Gradient descent with sparsification

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property

Full text

Pdf (805 KB)

Source

ACM International Conference Proceeding Series; Vol. 382 archive
Proceedings of the 26th Annual International Conference on Machine Learning table of contents

Montreal, Quebec, Canada

Pages 337-344

Year of Publication: 2009

ISBN:978-1-60558-516-1

Authors

Rahul Garg	IBM T. J. Watson Research Center, Yorktown Heights, NY
Rohit Khandekar	IBM T. J. Watson Research Center, Yorktown Heights, NY

Sponsors

: MITACS
: NSF
Microsoft Research : Microsoft Research

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 70, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1553374.1553417 What is a DOI?

ABSTRACT

We present an algorithm for finding an s-sparse vector x that minimizes the square-error ∥y -- Φx∥² where Φ satisfies the restricted isometry property (RIP), with isometric constant δ_2s < 1/3. Our algorithm, called GraDeS (Gradient Descent with Sparsification) iteratively updates x as: [EQUATION]

where γ > 1 and H_s sets all but s largest magnitude coordinates to zero. GraDeS converges to the correct solution in constant number of iterations. The condition δ_2s < 1/3 is most general for which a near-linear time algorithm is known. In comparison, the best condition under which a polynomial-time algorithm is known, is δ_2s < √2 -- 1.

Our Matlab implementation of GraDeS outperforms previously proposed algorithms like Subspace Pursuit, StOMP, OMP, and Lasso by an order of magnitude. Curiously, our experiments also uncovered cases where L1-regularized regression (Lasso) fails but GraDeS finds the correct solution.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Berinde, R., Indyk, P., & Ruzic, M. (2008). Practical near-optimal sparse recovery in the L1 norm. Allerton Conference on Communication, Control, and Computing. Monticello, IL.
	2	Blumensath, T., & Davies, M. E. (2008). Iterative hard thresholding for compressed sensing. Preprint.
	3	Candès, E., & Wakin, M. (2008). An introduction to compressive sampling. IEEE Signal Processing Magazine, 25, 21--30.
	4	Candès, E. J. (2008). The restricted isometry property and its implications for compressed sensing. Compte Rendus de l'Academie des Sciences, Paris, 1, 589--592.
	5	Candès, E. J., & Romberg, J. (2004). Practical signal recovery from random projections. SPIN Conference on Wavelet Applications in Signal and Image Processing.
	6	Candès, E. J., Romberg, J. K., & Tao, T. (2006). Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52, 489--509.
	7	Candès, E. J., & Tao, T. (2005). Decoding by linear programming. IEEE Transactions on Information Theory, 51, 4203--4215.
	8	Candès, E. J., & Tao, T. (2006). Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 52, 5406--5425.
	9	Scott Shaobing Chen , David L. Donoho , Michael A. Saunders, Atomic Decomposition by Basis Pursuit, SIAM Review, v.43 n.1, p.129-159, 2001 [doi>10.1137/S003614450037906X]
	10	Dai, W., & Milenkovic, O. (2008). Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity. ArXiv e-prints.
	11	Do, T. T., Gan, L., Nguyen, N., & Tran, T. D. (2008). Sparsity adaptive matching pursuit algorithm for practical compressed sensing. Asilomar Conference on Signals, Systems, and Computers. Pacific Grove, California.
	12	Donoho, D., & Others (2009). SparseLab: Seeking sparse solutions to linear systems of equations. http://sparselab.stanford.edu/.
	13	Donoho, D. L., & Tsaig, Y. (2006). Fast solution of L1 minimization problems when the solution may be sparse. Technical Report, Institute for Computational and Mathematical Engineering, Stanford University.
	14	Donoho, D. L., Tsaig, Y., Drori, I., & Starck, J.-L. (2006). Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit. Preprint.
	15	Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. Annals of Statistics, 32, 407--499.
	16	Figueiredo, M. A. T., & Nowak, R. D. (2005). A bound optimization approach to wavelet-based image deconvolution. IEEE International Conference on Image Processing (ICIP) (pp. 782--785).
	17	Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
	18	Jung, H., Ye, J. C., & Kim, E. Y. (2007). Improved k-t BLASK and k-t SENSE using FOCUSS. Phys. Med. Biol., 52, 3201--3226.
	19	Lustig, M. (2008). Sparse MRI. Ph.D Thesis, Stanford University.
	20	Ma, S., Yin, W., Zhang, Y., & Chakraborty, A. (2008). An efficient algorithm for compressed MR imaging using total variation and wavelets. IEEE Confererence on Computer Vision and Pattern Recognition (CVPR) (pp. 1--8).
	21	Mallat, S. G., & Zhang, Z. (1993). Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing, 3397--3415.
	22	B. K. Natarajan, Sparse Approximate Solutions to Linear Systems, SIAM Journal on Computing, v.24 n.2, p.227-234, April 1995 [doi>10.1137/S0097539792240406]
	23	Needell, & Tropp, J. A. (2008). CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 26, 301--321.
	24	Deanna Needell , Roman Vershynin, Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit, Foundations of Computational Mathematics, v.9 n.3, p.317-334, April 2009 [doi>10.1007/s10208-008-9031-3]
	25	Tyler Neylon , Dennis Shasha, Sparse solutions for linear prediction problems, New York University, New York, NY, 2006
	26	Ranzato, M., Boureau, Y.-L., & LeCun, Y. (2007). Sparse feature learning for deep belief networks. In Advances in neural information processing systems 20 (NIPS), 1185--1192. MIT Press.
	27	Sarvotham, S., Baron, D., & Baraniuk, R. (2006). Sudocodes - fast measurement and reconstruction of sparse signals. IEEE International Symposium on Information Theory (ISIT) (pp. 2804--2808). Seattle, Washington.
	28	Tropp, J. A., & Gilbert, A. C. (2007). Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Info. Theory, 53, 4655--4666.
	29	Wainwright, M. J., Ravikumar, P., & Lafferty, J. D. (2006). High-dimensional graphical model selection using l₁-regularized logistic regression. In Advances in neural information processing systems 19 (NIPS'06), 1465--1472. Cambridge, MA: MIT Press.
	30	Zou, H., Hastie, T., & Tibshirani, R. (2006). Sparse principal component analysis. Journal of Computational and Graphical Statistics, 15, 262--286.