Tight query complexity lower bounds for PCA via finite sample deformed wigner law.

Max Simchowitz, Ahmed El Alaoui, Benjamin Recht

Browse the full STOC paper archive.