Record Class CoSaMP

java.lang.Object
java.lang.Record
smile.cs.CoSaMP
Record Components:
x - the recovered sparse signal (length n).
support - the indices of the identified non-zero components.
iter - the number of iterations performed.
All Implemented Interfaces:
Serializable
public record CoSaMP(double[] x, int[] support, int iter) extends Record implements Serializable
Compressive Sampling Matching Pursuit (CoSaMP) for sparse signal recovery.

CoSaMP is a greedy recovery algorithm with provably near-optimal guarantees. Given an m × n measurement matrix A and observations y = A x, where x is k-sparse, CoSaMP recovers x in O(log(‖x‖/ε)) iterations, each of which requires only a matrix–vector product and a least-squares solve on a small sub-system.

The algorithm maintains a candidate support of size at most 2k, updates it via a "signal proxy" (the gradient of the data-fit term), prunes it back to size k, and re-estimates the signal coefficients by least-squares on the pruned support.

Algorithm sketch (one iteration)

  1. Proxy: e = A^T r where r = y − A x_old.
  2. Identify: merge support of x_old with the 2k largest entries of e; form union support Ω.
  3. Least-squares: b = arg min ‖y − A_Ω b‖₂.
  4. Prune: retain only the k largest entries of b; this gives the new support and estimate x_new.
  5. Residual: r = y − A x_new.

References

  1. D. Needell and J. A. Tropp, "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples", Appl. Comput. Harmon. Anal., 26(3):301–321, 2009.
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final record 
    CoSaMP.Options
    Hyperparameters for CoSaMP.

  • Constructor Summary

    Constructors
    Constructor
    Description
    CoSaMP(double[] x, int[] support, int iter)
    Creates an instance of a CoSaMP 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 CoSaMP
    fit(Matrix A, double[] y, int sparsity)
    Recovers a sparse signal via CoSaMP.
    static CoSaMP
    fit(Matrix A, double[] y, CoSaMP.Options options)
    Recovers a sparse signal via CoSaMP.
    final int
    hashCode()
    Returns a hash code value for this object.
    int
    iter()
    Returns the value of the iter record component.
    int[]
    support()
    Returns the value of the support 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

    • CoSaMP

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

  • Method Details

    • fit

      public static CoSaMP fit(Matrix A, double[] y, int sparsity)
      Recovers a sparse signal via CoSaMP.
      Parameters:
      A - the m × n measurement matrix.
      y - the m-dimensional measurement vector.
      sparsity - the target sparsity level k.
      Returns:
      the recovered signal.

    • fit

      public static CoSaMP fit(Matrix A, double[] y, CoSaMP.Options options)
      Recovers a sparse signal via CoSaMP.
      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

    • support

      public int[] support()
      Returns the value of the support record component.
      Returns:
      the value of the support record component

    • iter

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