- This event has passed.
Cheng Mao (Georgia Tech) – “Optimal Sparse Recovery of a Planted Vector in a Subspace”
Time: 2:00 pm – 3:15 pm
Date: 13th of September 2021
Place: en visio
Cheng Mao (Georgia Tech) – “Optimal Sparse Recovery of a Planted Vector in a Subspace”
Abstract: We consider the task of recovering a pN-sparse vector planted in an n-dimensional random subspace of R^N, given an arbitrary basis for the subspace. We give an improved analysis of (a slight variant of) a spectral method proposed by Hopkins, Schramm, Shi, and Steurer (STOC 2016), showing that it succeeds when np << sqrt(N). This condition improves upon the best known guarantees of any polynomial-time algorithm. Our analysis also applies to the dense case p=1, provided that the planted vector has entries sufficiently different from Gaussian. Furthermore, we give a matching lower bound, showing that when np >> sqrt(N), a general class of spectral methods fail to detect the planted vector. This yields a tight characterization of the power of this class of spectral methods and may suggest that no polynomial-time algorithm can succeed when np >> sqrt(N).
Organizers:
Cristina BUTUCEA (CREST), Alexandre TSYBAKOV (CREST), Karim LOUNICI (CMAP) , Jaouad MOURTADA (CREST)
Sponsors:
CREST-CMAP