Record Class BasisPursuit

java.lang.Object
java.lang.Record
smile.cs.BasisPursuit
Record Components:
x - the recovered sparse signal vector (length n).
iter - the total number of Newton (outer) iterations performed.
All Implemented Interfaces:
Serializable
public record BasisPursuit(double[] x, int iter) extends Record implements Serializable
Basis Pursuit Denoising (BPDN) via a log-barrier interior-point method.

Given an underdetermined linear system y = A*x + noise, where A is an m × n measurement matrix (m ≪ n), this class recovers the sparsest signal x by solving the convex L1-norm minimization known as Basis Pursuit Denoising: 

  minimise  ‖x‖₁
  subject to  ‖Ax − y‖₂ ≤ ε

When ε = 0 the problem reduces to exact Basis Pursuit: minimise ‖x‖₁ s.t. Ax = y.

The algorithm is a primal–dual log-barrier (interior-point) method that solves a sequence of unconstrained Newton sub-problems, each of which requires a linear solve. The inner linear system is solved with a preconditioned conjugate-gradient (PCG) method, making the overall approach suitable for large, sparse or implicit measurement matrices.

References

  1. E. J. Candès and T. Tao, "Near-optimal signal recovery from random projections: Universal encoding strategies?", IEEE Trans. Inf. Theory, 52(12):5406–5425, 2006.
  2. E. J. Candès, J. Romberg and T. Tao, "Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information", IEEE Trans. Inf. Theory, 52(2):489–509, 2006.
  3. S. S. Chen, D. L. Donoho and M. A. Saunders, "Atomic decomposition by basis pursuit", SIAM Rev., 43(1):129–159, 2001.
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final record 
    BasisPursuit.Options
    Hyperparameters for the log-barrier interior-point solver.

  • Constructor Summary

    Constructors
    Constructor
    Description
    BasisPursuit(double[] x, int iter)
    Creates an instance of a BasisPursuit record class.

  • Method Summary

    Modifier and Type
    Method
    Description
    final boolean
    equals(Object o)
    Indicates whether some other object is "equal to" this one.
    static BasisPursuit
    fit(Matrix A, double[] y)
    Recovers a sparse signal using Basis Pursuit (ε = 0).
    static BasisPursuit
    fit(Matrix A, double[] y, BasisPursuit.Options options)
    Recovers a sparse signal using Basis Pursuit Denoising.
    final int
    hashCode()
    Returns a hash code value for this object.
    int
    iter()
    Returns the value of the iter record component.
    final String
    toString()
    Returns a string representation of this record class.
    double[]
    x()
    Returns the value of the x record component.

    Methods inherited from class Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • BasisPursuit

      public BasisPursuit(double[] x, int iter)
      Creates an instance of a BasisPursuit record class.
      Parameters:
      x - the value for the x record component
      iter - the value for the iter record component

  • Method Details

    • fit

      public static BasisPursuit fit(Matrix A, double[] y)
      Recovers a sparse signal using Basis Pursuit (ε = 0).
      Parameters:
      A - the m × n measurement matrix.
      y - the m-dimensional measurement vector.
      Returns:
      the recovered signal.

    • fit

      public static BasisPursuit fit(Matrix A, double[] y, BasisPursuit.Options options)
      Recovers a sparse signal using Basis Pursuit Denoising.
      Parameters:
      A - the m × n measurement matrix.
      y - the m-dimensional measurement vector.
      options - solver hyperparameters.
      Returns:
      the recovered signal.

    • toString

      public final String toString()
      Returns a string representation of this record class. The representation contains the name of the class, followed by the name and value of each of the record components.
      Specified by:
      toString in class Record
      Returns:
      a string representation of this object

    • hashCode

      public final int hashCode()
      Returns a hash code value for this object. The value is derived from the hash code of each of the record components.
      Specified by:
      hashCode in class Record
      Returns:
      a hash code value for this object

    • equals

      public final boolean equals(Object o)
      Indicates whether some other object is "equal to" this one. The objects are equal if the other object is of the same class and if all the record components are equal. Reference components are compared with Objects::equals(Object,Object); primitive components are compared with the compare method from their corresponding wrapper classes.
      Specified by:
      equals in class Record
      Parameters:
      o - the object with which to compare
      Returns:
      true if this object is the same as the o argument; false otherwise.

    • x

      public double[] x()
      Returns the value of the x record component.
      Returns:
      the value of the x record component

    • iter

      public int iter()
      Returns the value of the iter record component.
      Returns:
      the value of the iter record component