All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation.
Jean BarbierNicolas MacrisCynthia RushPublished in: CoRR (2020)
Keyphrases
- phase transition
- constraint satisfaction
- random constraint satisfaction problems
- coefficient matrix
- satisfiability problem
- sparse matrix
- deep structure
- combinatorial problems
- randomly generated
- hard problems
- high dimensional
- sparse representation
- np complete
- singular value decomposition
- sat problem
- cellular automata
- np complete problems
- random instances
- mathematical programming
- upper bound
- boolean formulae
- learning algorithm