Fetching the paper…
Reading the bibliography…
We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown $n\times m$ matrix $A$ (for $m \geq n$) from examples of the form \[ y = Ax + e, \] where $x$ is a random vector in $\mathbb R^m$ with at most $\tau m$ nonzero coordinates, and $e$ is a random noise vector in $\mathbb R^n$ with bounded magnitude.
Ledyard R Tucker, Some mathematical notes on three-mode factor analysis , Psychometrika 31
1966
Earlier work this paper cites.
Joseph B Kruskal, Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics , Linear algebra and its applications 18
1977
Earlier work this paper cites.
Bruce Reznick, A quantitative version of Hurwitz’ theorem on the arithmetic-geometric inequality , J. reine angew. Math 377
1987
Earlier work this paper cites.
NZ Shor, An approach to obtaining global extremums in polynomial mathematical programming problems , Cybernetics and Systems Analysis 23
1987
Earlier work this paper cites.
Pierre Comon, Independent component analysis, a new concept? , Signal processing 36
1994
Earlier work this paper cites.
Alan Frieze, Mark Jerrum, and Ravi Kannan, Learning linear transformations , 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 359–368. MR 1450634
1996
Earlier work this paper cites.
Bruno A Olshausen and David J Field, Emergence of simple-cell receptive field properties by learning a sparse code for natural images , Nature 381
1996
Earlier work this paper cites.
Bruno A. Olshausen and David J. Field, Sparse coding with an overcomplete basis set: A strategy employed by v1? , Vision Research 37
1997
Earlier work this paper cites.
Franck Barthe, On a reverse form of the brascamp-lieb inequality , Inventiones mathematicae 134
1998
Earlier work this paper cites.
Y. Nesterov, Squared functional systems and optimization problems , High performance optimization 13
2000
Earlier work this paper cites.
Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Ph.D. thesis, California Institute of Technology, 2000
2000
Earlier work this paper cites.
Jürgen Forster, A linear lower bound on the unbounded error probabilistic communication complexity , IEEE Conference on Computational Complexity, IEEE Computer Society, 2001, pp. 100–106
2001
Earlier work this paper cites.
Dima Grigoriev, Linear lower bound on degrees of positivstellensatz calculus proofs for the parity , Theor. Comput. Sci. 259
2001
Earlier work this paper cites.
Jean B. Lasserre, Global optimization with polynomials and the problem of moments , SIAM Journal on Optimization 11
2001
Earlier work this paper cites.
Andrew C Doherty, Pablo A Parrilo, and Federico M Spedalieri, Distinguishing separable and entangled states , Physical Review Letters 88
2002
Cited alongside, same era.
Didier Henrion and Andrea Garulli, Positive polynomials in control , vol. 312, Springer, 2005
2005
Cited alongside, same era.
Emmanuel J Candes, Justin K Romberg, and Terence Tao, Stable signal recovery from incomplete and inaccurate measurements , Communications on pure and applied mathematics 59
2006
Cited alongside, same era.
David L Donoho, Compressed sensing , Information Theory, IEEE Transactions on 52
2006
Cited alongside, same era.
Michael Elad and Michal Aharon, Image denoising via sparse and redundant representations over learned dictionaries , Image Processing, IEEE Transactions on 15
2006
Cited alongside, same era.
Sanjeev Arora, Rong Ge, and Ankur Moitra, Learning topic models - going beyond svd , FOCS, IEEE Computer Society, 2012, pp. 1–10
2012
Later among the works it cites.
Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications , STOC, 2012, pp. 307–326
2012
Later among the works it cites.
Daniel A. Spielman, Huan Wang, and John Wright, Exact recovery of sparsely-used dictionaries , Journal of Machine Learning Research - Proceedings Track 23
2012
Later among the works it cites.
2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Phong Q. Nguyen and Oded Regev, Learning a parallelepiped: Cryptanalysis of ggh and ntru signatures , J. Cryptology 22
2006
Cited alongside, same era.
Andreas Argyriou Theodoros Evgeniou and Massimiliano Pontil, Multi-task feature learning , Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference, vol. 19, MIT Press, 2007, pp. 41–48
2007
Cited alongside, same era.
John Harrison, Verifying nonlinear real formulas via sums of squares , Theorem Proving in Higher Order Logics, Springer, 2007, pp. 102–118
2007
Cited alongside, same era.
Lieven De Lathauwer, Joséphine Castaing, and Jean-François Cardoso, Fourth-order cumulant-based blind identification of underdetermined mixtures , IEEE Transactions on Signal Processing 55
2007
Cited alongside, same era.
Y Marc’Aurelio Ranzato, Lan Boureau, and Yann LeCun, Sparse feature learning for deep belief networks , Advances in neural information processing systems 20
2007
Cited alongside, same era.
Julien Mairal, Marius Leordeanu, Francis Bach, Martial Hebert, and Jean Ponce, Discriminative sparse image models for class-specific edge detection and image interpretation , Computer Vision–ECCV 2008, Springer, 2008, pp. 43–56
2008
Cited alongside, same era.
Grant Schoenebeck, Linear level Lasserre lower bounds for certain k-CSPs , FOCS, 2008, pp. 593–602
2008
Cited alongside, same era.
2013
Later among the works it cites.
L. Demanet and P. Hand, Recovering the Sparsest Element in a Subspace , October 2013, Arxiv preprint 1310.1654
2013
Later among the works it cites.
2014
Closest in time.
Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan, Smoothed analysis of tensor decompositions , STOC, 2014
2014
Closest in time.
Aditya Bhaskara, Moses Charikar, and Aravindan Vijayaraghavan, Uniqueness of tensor decompositions with applications to polynomial identifiability , COLT (Maria-Florina Balcan and Csaba Szepesvári, eds.), JMLR Proceedings, vol. 35, JMLR.org, 2014, pp. 742–778
2014
Closest in time.
B. Barak, J.A. Kelner, and D. Steurer, Rounding sum of squares relaxations , STOC, 2014
2014
Closest in time.
Boaz Barak and David Steurer, Sum-of-squares proofs and the quest toward optimal algorithms , Proceedings of International Congress of Mathematicians (ICM), 2014, To appear
2014
Closest in time.
Péter E Frenkel and Péter Horváth, Minkowski’s inequality and sums of squares , Central European Journal of Mathematics 12
2014
Closest in time.
Navin Goyal, Santosh Vempala, and Ying Xiao, Fourier pca , STOC, 2014, Also available as arXiv report 1306.5825
2014
Closest in time.