OCP: a greedy projection method for row-sparse representations of minimum-norm solutions

In this paper, we propose a greedy projection method, termed orthogonal constraint pursuit (OCP), for identifying a small set of rows of a consistent linear system $Ax=b$ whose span contains the minimum-norm solution $x^*$, along with the coefficients of that representation. The method successively activates the most violated constraint, and then projects the iterate onto the intersection of all activated constraints. We prove that OCP is equivalent to OMP applied to the dictionary $A^T$ and the signal $x^*$, and that it terminates in at most rank(A) iterations. When $x^*$ is a linear combination of $s$ rows of a matrix whose rows are independent and uniformly distributed on the unit sphere, OCP identifies those rows in exactly $s$ iterations with probability $1-O(m^{-1})$, provided that $n\ge Cs\ln m$ for a sufficiently large constant $C$. We also derive a variant of OCP with constraint removal for hard-margin support vector machines with regularized bias, which returns the support vectors, along with the multipliers that satisfy the KKT conditions. Numerical results on both real and synthetic problems demonstrate the identification of representing rows and the regime in which it is competitive with Krylov subspace methods.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-17
DOI
https://doi.org/10.48550/arxiv.2611.22253
Primary Topic
Sparse and Compressive Sensing Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

OCP: a greedy projection method for row-sparse representations of minimum-norm solutions

Deanna M. Needell, Qing-Wen Wang, Tao Li
arXiv (Cornell University)
Sparse and Compressive Sensing Techniques
preprint

OCP: a greedy projection method for row-sparse representations of minimum-norm solutions

Deanna M. Needell, Qing-Wen Wang, Tao Li
preprint en

Abstract

In this paper, we propose a greedy projection method, termed orthogonal constraint pursuit (OCP), for identifying a small set of rows of a consistent linear system $Ax=b$ whose span contains the minimum-norm solution $x^*$, along with the coefficients of that representation. The method successively activates the most violated constraint, and then projects the iterate onto the intersection of all activated constraints. We prove that OCP is equivalent to OMP applied to the dictionary $A^T$ and the signal $x^*$, and that it terminates in at most rank(A) iterations. When $x^*$ is a linear combination of $s$ rows of a matrix whose rows are independent and uniformly distributed on the unit sphere, OCP identifies those rows in exactly $s$ iterations with probability $1-O(m^{-1})$, provided that $n\ge Cs\ln m$ for a sufficiently large constant $C$. We also derive a variant of OCP with constraint removal for hard-margin support vector machines with regularized bias, which returns the support vectors, along with the multipliers that satisfy the KKT conditions. Numerical results on both real and synthetic problems demonstrate the identification of representing rows and the regime in which it is competitive with Krylov subspace methods.

arXiv (Cornell University)
Sparse and Compressive Sensing Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon