- Optimality and sub-optimali...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2016
Optimality and sub-optimality of PCA for spiked random matrix models
Speaker:
Alex Wein
, MIT
Date: Wednesday, October 19, 2016
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-D507
Event Type:
Room Description:
Host: Pritish Kamath and Akshay Degwekar
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Speaker URL: None
Speaker Photo:
None
Reminders to:
seminars@csail.mit.edu, theory-seminars@csail.mit.edu
Reminder Subject:
TALK: Alex Wein:Optimality and sub-optimality of PCA for spiked random matrix models
Abstract: Classical results from random matrix theory state that if a random (Wigner or Wishart) matrix is perturbed by a planted rank-1 signal (or "spike"), this spike affects the top eigenvalue if and only if the size of the spike exceeds a particular threshold. In particular, above this threshold the top eigenvalue is a reliable test to distinguish the spiked and un-spiked models. We consider the question of whether this eigenvalue test is optimal, or whether there is some other statistical test that can succeed below the eigenvalue threshold.
We answer these types of questions using a simple and widely-applicable technique associated with the statistical notion of "contiguity." Namely, by computing a particular second moment, one can show that two models are contiguous and therefore cannot be reliably distinguished.
Our results include:
i) For the Gaussian Wigner ensemble, we show that PCA achieves the optimal detection threshold for a variety of natural priors for the spike.
ii) For any non-Gaussian Wigner ensemble, we show that PCA is always sub-optimal for detection (contrary to the notion of universality from random matrix theory). However, a variant of PCA achieves the optimal threshold (for natural priors) by pre-transforming the matrix entrywise.
iii) For the Wishart ensemble we show that in some regimes, inefficient algorithms can succeed below the PCA threshold, whereas no known efficient algorithm achieves this.
Based on joint work with Amelia Perry, Afonso Bandeira, and Ankur Moitra. Available at https://arxiv.org/abs/1609.05573.
Research Areas:
Impact Areas:
Created by Rebecca Yadegar at Tuesday, October 11, 2016 at 1:39 PM.