AI & ML
OCP: a greedy projection method for row-sparse representations of minimum-norm solutions
arXiv cs.NA0 views
arXiv:2611.22253v1 Announce Type: new 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.
Source:https://arxiv.org/abs/2611.22253PreviousAn Explicit Parallelizable Robin-Robin Splitting Scheme for Navier-Stokes-Naghdi Shell InteractionNextNonlocal regularization of sharp-crack energetics: a variational bridge from Griffith geometry to emergent constitutive degradation
Related posts
How Far Behind Are Open Weights, Measured
0dev.to
Claude was trained on protein sequences at scale
0Hacker News
Pretraining vs post-training: one apple problem, four learning signals
0dev.to Beginners
Bitcoin Recovery Expert USA: Professional Crypto Asset Recovery with META TECH RETRIEVE PRO
0dev.to Beginners
Hugging Face Switches Its Inference Providers to OpenRouter Routing
0dev.to OpenSource
Still confused about Git vs GitHub?
0dev.to Git