Built on

Andreas Goerdt and Michael Krivelevich, Efficient recognition of random unsatisfiable k-sat instances by spectral methods , STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings, 2001, pp. 294–304
2001
Earlier work this paper cites.
Joel Friedman, Andreas Goerdt, and Michael Krivelevich, Recognizing more unsatisfiable random k-sat instances efficiently , SIAM J. Comput. 35
2005
Earlier work this paper cites.
Uriel Feige, Jeong Han Kim, and Eran Ofek, Witnesses for non-satisfiability of dense random 3cnf formulas , FOCS, 2006, pp. 497–508
2006
Earlier work this paper cites.
Uriel Feige and Eran Ofek, Easily refutable subformulas of large random 3cnf formulas , Theory of Computing 3
2007
Earlier work this paper 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 (Howard J. Karloff and Toniann Pitassi, eds.), ACM, 2012, pp. 307–326
2012
Earlier work this paper cites.
Andrew C Doherty and Stephanie Wehner, Convergence of sdp hierarchies for polynomial optimization on the hypersphere , arXiv preprint arXiv:1210.5048 (2012)
Original
2012
Earlier work this paper cites.
Terence Tao, Topics in random matrix theory , vol. 132, American Mathematical Soc., 2012
2012
Earlier work this paper cites.
Joel A. Tropp, User-friendly tail bounds for sums of random matrices , Foundations of Computational Mathematics 12
2012
Earlier work this paper cites.

Similar

Anima Anandkumar, Rong Ge, Daniel Hsu, and Sham M. Kakade, A tensor spectral approach to learning mixed membership community models , CoRR abs/1302.2684
Original
2013
Cited alongside, same era.
Boaz Barak, Guy Kindler, and David Steurer, On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction , ITCS, 2013, pp. 197–214
2013
Cited alongside, same era.
Quentin Berthet and Philippe Rigollet, Complexity theoretic lower bounds for sparse principal component detection , COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, 2013, pp. 1046–1066
2013
Cited alongside, same era.
Ryan O’Donnell and Yuan Zhou, Approximability and proof complexity , SODA (Sanjeev Khanna, ed.), SIAM, 2013, pp. 1537–1556
2013
Cited alongside, same era.

Then

Boaz Barak, Jonathan A. Kelner, and David Steurer, Dictionary learning and tensor decomposition via the sum-of-squares method , CoRR abs/1407.1543
Original
2014
Later among the works it cites.
Boaz Barak and David Steurer, Sum-of-squares proofs and the quest toward optimal algorithms , CoRR abs/1404.5236
Original
2014
Later among the works it cites.
Andrea Montanari and Emile Richard, A statistical model for tensor pca , Advances in Neural Information Processing Systems, 2014, pp. 2897–2905
2014
Later among the works it cites.
Andrea Montanari, Daniel Reichman, and Ofer Zeitouni, On the limitation of spectral methods: From the gaussian hidden clique problem to rank one perturbations of gaussian tensors , arXiv preprint arXiv:1411.6149 (2014)
Original
2014
Later among the works it cites.
Ryota Tomioka and Taiji Suzuki, Spectral norm of random tensors , arXiv preprint arXiv:1407.1870 (2014)

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2015

Tensor principal component analysis via sum-of-squares proofs

Hopkins, Samuel B., Shi, Jonathan, Steurer, David

Understand

We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order-$3$ tensor $T$ of the form $T = \tau \cdot v_0^{\otimes 3} + A$, where $\tau \geq 0$ is a signal-to-noise ratio, $v_0$ is a unit vector, and $A$ is a random noise tensor, the goal is to recover the planted vector $v_0$.

For the case that $A$ has iid standard Gaussian entries, we give an efficient algorithm to recover $v_0$ whenever $\tau \geq \omega(n^{3/4} \log(n)^{1/4})$, and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of $A$.
The previous best algorithms with provable guarantees required $\tau \geq \Omega(n)$.
In the regime $\tau \leq o(n)$, natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down (in the sense that their integrality gap is large).

Built on

Andreas Goerdt and Michael Krivelevich, Efficient recognition of random unsatisfiable k-sat instances by spectral methods , STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings, 2001, pp. 294–304
2001
Earlier work this paper cites.
Joel Friedman, Andreas Goerdt, and Michael Krivelevich, Recognizing more unsatisfiable random k-sat instances efficiently , SIAM J. Comput. 35
2005
Earlier work this paper cites.
Uriel Feige, Jeong Han Kim, and Eran Ofek, Witnesses for non-satisfiability of dense random 3cnf formulas , FOCS, 2006, pp. 497–508
2006
Earlier work this paper cites.
Uriel Feige and Eran Ofek, Easily refutable subformulas of large random 3cnf formulas , Theory of Computing 3
2007
Earlier work this paper 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 (Howard J. Karloff and Toniann Pitassi, eds.), ACM, 2012, pp. 307–326
2012
Earlier work this paper cites.
Andrew C Doherty and Stephanie Wehner, Convergence of sdp hierarchies for polynomial optimization on the hypersphere , arXiv preprint arXiv:1210.5048 (2012)
Original
2012
Earlier work this paper cites.
Terence Tao, Topics in random matrix theory , vol. 132, American Mathematical Soc., 2012
2012
Earlier work this paper cites.
Joel A. Tropp, User-friendly tail bounds for sums of random matrices , Foundations of Computational Mathematics 12
2012
Earlier work this paper cites.

Similar

Anima Anandkumar, Rong Ge, Daniel Hsu, and Sham M. Kakade, A tensor spectral approach to learning mixed membership community models , CoRR abs/1302.2684
Original
2013
Cited alongside, same era.
Boaz Barak, Guy Kindler, and David Steurer, On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction , ITCS, 2013, pp. 197–214
2013
Cited alongside, same era.
Quentin Berthet and Philippe Rigollet, Complexity theoretic lower bounds for sparse principal component detection , COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, 2013, pp. 1046–1066
2013
Cited alongside, same era.
Ryan O’Donnell and Yuan Zhou, Approximability and proof complexity , SODA (Sanjeev Khanna, ed.), SIAM, 2013, pp. 1537–1556
2013
Cited alongside, same era.

Then

Boaz Barak, Jonathan A. Kelner, and David Steurer, Dictionary learning and tensor decomposition via the sum-of-squares method , CoRR abs/1407.1543
Original
2014
Later among the works it cites.
Boaz Barak and David Steurer, Sum-of-squares proofs and the quest toward optimal algorithms , CoRR abs/1404.5236
Original
2014
Later among the works it cites.
Andrea Montanari and Emile Richard, A statistical model for tensor pca , Advances in Neural Information Processing Systems, 2014, pp. 2897–2905
2014
Later among the works it cites.
Andrea Montanari, Daniel Reichman, and Ofer Zeitouni, On the limitation of spectral methods: From the gaussian hidden clique problem to rank one perturbations of gaussian tensors , arXiv preprint arXiv:1411.6149 (2014)
Original
2014
Later among the works it cites.
Ryota Tomioka and Taiji Suzuki, Spectral norm of random tensors , arXiv preprint arXiv:1407.1870 (2014)

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky, Tensor decompositions for learning latent variable models , Journal of Machine Learning Research 15

2014

Cited alongside, same era.

Anima Anandkumar, Rong Ge, and Majid Janzamin, Analyzing tensor power method dynamics: Applications to learning overcomplete latent variable models , CoRR abs/1411.1488

Original

2014

Cited alongside, same era.

Animashree Anandkumar, Rong Ge, and Majid Janzamin, Guaranteed non-orthogonal tensor decomposition via alternating rank-1 updates , CoRR abs/1402.5180

Original

2014

Cited alongside, same era.

Roman Vershynin, Introduction to the non-asymtotic analysis of random matrices , 210–268

Cited in the paper.