Runtime lower-bound conjecture for sparse PCA in the hard regime
Statement
Let be a matrix, let have exactly nonzero entries, and observe , with . Exact recovery means outputting with probability tending to as .
Sparse PCA runtime conjecture. For any in the hard regime
any algorithm for exact recovery requires runtime
This conjecture proposes a precise computational barrier in the regime where exact recovery is believed to be information-theoretically possible but no polynomial-time algorithm is known. Existing evidence includes reductions from planted clique, failure of approximate message passing, sum-of-squares lower bounds, and the overlap gap property, but those results do not establish this precise optimal-runtime expression.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.