Fetching the paper…
Reading the bibliography…
This paper deals with the computational complexity of conditions which guarantee that the NP-hard problem of finding the sparsest solution to an underdetermined linear system can be solved by efficient algorithms.
M. J. Piff, and D. J. A. Welsh, “On the vector representation of matroids,” J. London Math. Soc. , vol. 2, no. 2, pp. 284–288, 1970
1970
Earlier work this paper cites.
R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of computer computations , R. Miller and J. W. Thatcher, Eds. New York: Plenum Press, 1972, pp. 85–103
1972
Earlier work this paper cites.
C. van Nuffelen, “On the incidence matrix of a graph,” IEEE Trans. Circuits Syst. , vol. CAS-23, no. 9, p. 572, Sept. 1976
1976
Earlier work this paper cites.
A. Itai and M. Rodeh, “Finding a minimum circuit in a graph,” SIAM J. Comput. , vol. 7, no. 4, pp. 413–423, 1978
1978
Earlier work this paper cites.
E. R. Berlekamp, R. J. McEliece, and H. C. A. van Tilborg, “On the inherent intractability of certain coding problems,” IEEE Trans. Inf. Theory , vol. IT-24, no. 3, pp. 384–386, May 1978
1978
Earlier work this paper cites.
M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness . San Francisco, CA: W. H. Freeman and Company, 1979
1979
Earlier work this paper cites.
S. T. McCormick, “A combinatorial approach to some sparse matrix problems,” Ph.D. dissertation, Stanford University, 1983
1983
Earlier work this paper cites.
T. F. Coleman and A. Pothen, “The null space problem I. Complexity,” SIAM J. Algebra. Discr. , vol. 7, no. 4, pp. 527–537, 1986
1986
Earlier work this paper cites.
J. F. Queiró, “On the interlacing property for singular values and eigenvalues,” Linear Algebra Appl. , vol. 97, pp. 23–28, 1987
1987
Earlier work this paper cites.
S. Friedland, “Bounds on the Spectral Radius of Graphs with e e Edges,” Lin. Alg. Appl. , vol. 101, pp. 81–86, 1988
1988
Earlier work this paper cites.
P. E. Gill, W. Murray, and M. H. Wright, Numerical Linear Algebra and Optimization , vol. 1, Redwood City, CA, USA: Addison-Wesley Publishing Company, 1991
1991
Earlier work this paper cites.
J. G. Oxley, Matroid theory , 1st ed., ser. Oxford Graduate Texts in Mathematics, vol. 3. New York, NY, USA: Oxford University Press, 1992
1992
Earlier work this paper cites.
M. Grötschel, L. Lovász, and A. Schrijver, Geometric algorithms and combinatorial optimization , 2nd ed., ser. Algorithms and Combinatorics, vol. 2. Heidelberg, Germany: Springer, 1993
1993
Earlier work this paper cites.
B. K. Natarajan, “Sparse approximate solutions to linear systems,” SIAM J. Comput. , vol. 24, no. 2, pp. 227–234, Apr. 1995
1995
Earlier work this paper cites.
L. Khachiyan, “On the complexity of approximating extremat determinants in matrices,” J. Complexity , vol. 11, pp. 138–153, 1995
1995
Earlier work this paper cites.
E. Amaldi and V. Kann, “The complexity and approximability of finding maximum feasible subsystems of linear relations,” Theoret. Comput. Sci. , vol. 147, no. 1–2, pp. 181-210, Aug. 1995
1995
Earlier work this paper cites.
G. H. Golub and C. F. van Loan, Matrix Computations , 3rd ed. Baltimore, MD, USA: Johns Hopkins University Press, 1996
1996
Earlier work this paper cites.
H. P. Hirst and W. T. Macey, “Bounding the roots of polynomials,” The College Mathematics Journal , vol. 28, no. 4, pp. 292–295, Sept. 1997
1997
Earlier work this paper cites.
A. Vardy, “The intractability of computing the minimum distance of a code,” IEEE Trans. Inf. Theory , vol. 43, no. 6, pp. 1757–1766, Nov. 1997
1997
Earlier work this paper cites.
S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM J. Sci. Comput. , vol. 20, no. 1, pp. 33–61, Aug. 1998
1998
Earlier work this paper cites.
E. Amaldi and V. Kann, “On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems,” Theor. Comput. Sci. , vol. 209, pp. 237–260, 1998
1998
Cited alongside, same era.
S. De Marchi, “Generalized Vandermonde determinants, Toeplitz matrices and Schur functions,”, Tech. Rep. Ergebnisberichte Angewandte Mathematik , vol. 176, Universität Dortmund, 1999
1999
Cited alongside, same era.
D. L. Donoho and X. Huo, “Uncertainty principles and ideal atomic decomposition,” IEEE Trans. Inf. Theory , vol. 47, no. 7, pp. 2845–2862, Nov. 2001
2001
Cited alongside, same era.
R. Gribonval and M. Nielsen, “Sparse representations in unions of bases,” IEEE Trans. Inf. Theory , vol. 49, no. 12, pp. 3320–3325, Dec. 2003
2003
Cited alongside, same era.
D. L. Donoho and M. Elad, “Optimally sparse representation in general (non-orthogonal) dictionaries via ℓ 1 \ell^{1} minimization,” P. Natl. Acad. Sci. USA , vol. 100, no. 5, pp. 2197–2202, Mar. 2003
S. Foucart and M.-J. Lai, “Sparsest solutions of underdetermined linear systems via ℓ q \ell_{q} -minimization for 0 ≤ q ≤ 1 0\leq q\leq 1 ,” Appl. Comput. Harmon. A. , vol. 26, pp. 395–407, 2009
2009
Later among the works it cites.
A. M. Bruckstein, D. L. Donoho, and M. Elad, “From sparse solutions of systems of equations to sparse modeling of signals and images,” SIAM Rev. , vol. 51, no. 1, pp. 34–81, 2009
2009
Later among the works it cites.
M. Elad, Sparse and redundant representations: From theory to applications in signal and image processing . Heidelberg, Germany: Springer, 2010
2010
Later among the works it cites.
T. T. Cai, L. Wang, and G. Xu, “New bounds for restricted isometry constants,” IEEE Trans. Inf. Theory , vol. 56, no. 9, pp. 4388–4394, Sept. 2010
2010
Later among the works it cites.
B. Bah and J. Tanner, “Improved bounds on restricted isometry constants for Gaussian matrices,” SIAM J. Matrix Anal. A. , vol. 31, no. 5, pp. 2882–2892, 2010
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2003
Cited alongside, same era.
A. Chistov, H. Fournier, L. Gurvits, and P. Koiran, “Vandermonde Matrices, NP-Completeness, and Transversal Subspaces,” Found. Comput. Math. , vol. 3, no. 4, pp. 421–427, Oct. 2003
2003
Cited alongside, same era.
J. A. Tropp, “Greed is good: Algorithmic results for sparse approximation,” IEEE Trans. Inf. Theory , vol. 50, pp. 2231–2242, Oct. 2004
2004
Cited alongside, same era.
E. Candès and T. Tao, “Decoding by linear programming,” IEEE Trans. Inf. Theory , vol. 51, pp. 4203–4215, Dec. 2005
2005
Cited alongside, same era.
D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory , vol. 52, no. 4, pp. 1289–1306, Apr. 2006
2006
Cited alongside, same era.
R. A. DeVore, “Deterministic constructions of compressed sensing matrices,” J. Complexity , vol. 23, pp. 918–925, Aug. 2007
2007
Cited alongside, same era.
A. d’Aspremont, L. E. Ghaoui, M. I. Jordan, and G. R. G. Lanckriet, “A direct formulation for sparse PCA using semidefinite programming,” SIAM Rev. , vol. 49, no. 3, pp. 434–448, 2007
2007
Cited alongside, same era.
R. G. Baraniuk, M. A. Davenport, R. A. DeVore, and M. B. Wakin, “A simple proof of the restricted isometry property for random matrices,” Constr. Approx. , vol. 28, no. 3, pp. 253–263, 2008
2008
Cited alongside, same era.
2010
Later among the works it cites.
M. A. Davenport and M. B. Wakin, “Analysis of orthogonal matching pursuit using the restricted isometry property,” IEEE Trans. Inf. Theory , vol. 56, no. 9, pp. 4395–4401, Sep. 2010
2010
Later among the works it cites.
M. Fornasier and H. Rauhut, “Compressive sensing,” in Handbook of mathematical methods in imaging , O. Scherzer, Ed. Berlin, Heidelberg, New York: Springer, 2011, pp. 187–228
2011
Later among the works it cites.
J. D. Blanchard, C. Cartis, and J. Tanner, “Compressed sensing: How sharp is the RIP?” SIAM Rev. , vol. 53, no. 1, pp. 105–125, Feb. 2011
2011
Later among the works it cites.
2011
Later among the works it cites.
2011
Later among the works it cites.
A. Juditsky and A. Nemirovski, “On verifiable sufficient conditions for sparse signal recovery via ℓ 1 \ell_{1} minmization,” Math. Program. , vol. 127, no. 1, pp. 57–88, 2011
2011
Later among the works it cites.
A. d’Aspremont and L. E. Ghaoui, “Testing the nullspace property using semidefinite programming,” Math. Program. , vol. 127, no. 1, pp. 123–144, 2011
2011
Later among the works it cites.
2011
Later among the works it cites.
2012
Closest in time.
A. E. Brouwer and W. H. Haemers, Spectra of Graphs , ser. Universitext, vol. XIII. Berlin, Germany: Springer, 2012
2012
Closest in time.
2012
Closest in time.
2013
Closest in time.
A. S. Bandeira, E. Dobriban, D. G. Mixon, and W. F. Sawin, “Certifying the restricted isometry property is hard,” IEEE Trans. Inf. Theory , vol. 59, no. 6, pp. 3448–3450, Jun. 2013
2013
Closest in time.
R. Luss and M. Teboulle, “Conditional Gradient Algorithms for Rank-One Matrix Approximations with a Sparsity Constraint,” SIAM Rev. , vol. 55, no. 1, pp. 65–98, 2013
2013
Closest in time.