Record Class OMP

java.lang.Object
java.lang.Record
smile.cs.OMP
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 OMP(double[] x, int[] support, int iter) extends Record implements Serializable
Orthogonal Matching Pursuit (OMP) for sparse signal recovery.

OMP is a greedy algorithm that iteratively selects the column of the measurement matrix A most correlated with the current residual, augments the support set, and then re-solves a least-squares problem on the active set to refine the coefficient estimates.

Given an underdetermined system y = A*x where x is known to be k-sparse, OMP reconstructs x in exactly k steps (assuming the restricted isometry property holds with δ_{2k} < √2 − 1).

The noisy extension terminates when ‖residual‖₂ ≤ tolerance.

Complexity

  • Per iteration: O(m·n) for the correlation step plus O(m·k²) for the least-squares step (via QR update).
  • Total: O(k·(m·n + m·k²)).

References

  1. J. A. Tropp and A. C. Gilbert, "Signal recovery from random measurements via orthogonal matching pursuit", IEEE Trans. Inf. Theory, 53(12):4655–4666, 2007.
  2. G. Davis, S. Mallat and M. Avellaneda, "Adaptive greedy approximations", Constr. Approx., 13(1):57–98, 1997.
See Also:

  • Nested Class Summary

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    OMP(double[] x, int[] support, int iter)
    Creates an instance of a OMP 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 OMP
    fit(Matrix A, double[] y, int sparsity)
    Recovers a sparse signal via Orthogonal Matching Pursuit.
    static OMP
    fit(Matrix A, double[] y, OMP.Options options)
    Recovers a sparse signal via Orthogonal Matching Pursuit.
    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

    • OMP

      public OMP(double[] x, int[] support, int iter)
      Creates an instance of a OMP 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 OMP fit(Matrix A, double[] y, int sparsity)
      Recovers a sparse signal via Orthogonal Matching Pursuit.
      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 OMP fit(Matrix A, double[] y, OMP.Options options)
      Recovers a sparse signal via Orthogonal Matching Pursuit.
      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