All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation.
Jean BarbierNicolas MacrisCynthia RushPublished in: NeurIPS (2020)
Keyphrases
- phase transition
- coefficient matrix
- random constraint satisfaction problems
- constraint satisfaction
- satisfiability problem
- randomly generated
- high dimensional
- combinatorial problems
- hard problems
- random instances
- sparse matrix
- np complete
- cellular automata
- regularized regression
- deep structure
- low rank
- np complete problems
- reinforcement learning
- random graphs
- singular value decomposition
- sparse representation
- computational complexity
- search algorithm