orthogonal_mp

sklearn.linear_model.orthogonal_mp(X, y, *, n_nonzero_coefs=None, tol=None, precompute=False, copy_X=True, return_path=False, return_n_iter=False)

Orthogonal Matching Pursuit (OMP).

Solves n_targets Orthogonal Matching Pursuit problems. Each instance of the problem fits a linear model with constraints imposed on the number of non-zero coefficients (i.e. the \(\\ell_0\) pseudo-norm) using n_nonzero_coefs:

\[\underset{w}{\operatorname{arg\,min\,}} ||y - Xw||^2_2 \text{ subject to } ||w||_0 \leq n_{\text{nonzero_coefs}}\]

When parametrized by error using the parameter tol:

\[\underset{w}{\operatorname{arg\,min\,}} ||w||_0 \text{ subject to } ||y - Xw||^2_2 \leq tol\]

Read more in the User Guide.

Parameters:

Xarray-like of shape (n_samples, n_features)

Input data. Columns are assumed to have unit norm.

yndarray of shape (n_samples,) or (n_samples, n_targets)

Input targets.

n_nonzero_coefsint, default=None

Maximum number of non-zero entries in the solution. If None (by default) this value is set to 10% of n_features.

tolfloat, default=None

Maximum squared norm of the residual. If not None, overrides n_nonzero_coefs.

precompute‘auto’ or bool, default=False

Whether to perform precomputations. Improves performance when n_targets or n_samples is very large.

copy_Xbool, default=True

Whether the design matrix X must be copied by the algorithm. A false value is only helpful if X is already Fortran-ordered, otherwise a copy is made anyway.

return_pathbool, default=False

Whether to return every value of the nonzero coefficients along the forward path. Useful for cross-validation.

return_n_iterbool, default=False

Whether or not to return the number of iterations.

Returns:

coefndarray of shape (n_features,) or (n_features, n_targets)

Coefficients of the OMP solution. If return_path=True, this contains the whole coefficient path. In this case its shape is (n_features, n_features) or (n_features, n_targets, n_features) and iterating over the last axis generates coefficients in increasing order of active features.

n_itersarray-like or int

Number of active features across every target. Returned only if return_n_iter is set to True.

See also

OrthogonalMatchingPursuit

Orthogonal Matching Pursuit model.

orthogonal_mp_gram

Solve OMP problems using Gram matrix and the product X.T * y.

lars_path

Compute Least Angle Regression or Lasso path using LARS algorithm.

sklearn.decomposition.sparse_encode

Sparse coding.

Notes

Orthogonal matching pursuit was introduced in S. Mallat, Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing, Vol. 41, No. 12. (December 1993), pp. 3397-3415. (https://www.di.ens.fr/~mallat/papiers/MallatPursuit93.pdf)

This implementation is based on Rubinstein, R., Zibulevsky, M. and Elad, M., Efficient Implementation of the K-SVD Algorithm using Batch Orthogonal Matching Pursuit Technical Report - CS Technion, April 2008. https://www.cs.technion.ac.il/~ronrubin/Publications/KSVD-OMP-v2.pdf

Examples

>>> from sklearn.datasets import make_regression
>>> from sklearn.linear_model import orthogonal_mp
>>> X, y = make_regression(noise=4, random_state=0)
>>> coef = orthogonal_mp(X, y)
>>> coef.shape
(100,)
>>> X[:1,] @ coef
array([-78.68])