betaFeedback

WorksMathematics

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

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=bAx=b whose span contains the minimum-norm solution x∗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 ATA^T and the signal x∗x^*, and that it terminates in at most rank(A) iterations. When x∗x^* is a linear combination of ss rows of a matrix whose rows are independent and uniformly distributed on the unit sphere, OCP identifies those rows in exactly ss iterations with probability 1−O(m−1)1-O(m^{-1}), provided that n≥Csln⁡mn\ge Cs\ln m for a sufficiently large constant CC. 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.

Paper details

vlnc:W_rkzvmbqy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…