An atomic matrix norm regularizer for sparse phase retrieval and PCA

ACO Student Seminar
Friday, September 24, 2021 - 1:00pm for 1 hour (actually 50 minutes)
Skiles 314
Andrew Mcrae – Georgia Tech ECE –
Abhishek Dhawan

Please Note: Stream online at

We present a mixed atomic matrix norm that, when used as regularization in optimization problems, promotes low-rank matrices with sparse factors. We show that in convex lifted formulations of sparse phase retrieval and sparse principal component analysis (PCA), this norm provides near-optimal sample complexity and error rate guarantees. Since statistically optimal sparse PCA is widely believed to be NP-hard, this leaves open questions about how practical it is to compute and optimize this atomic norm. Motivated by convex duality analysis, we present a heuristic algorithm in the case of sparse phase retrieval and show that it empirically matches existing state-of-the-art algorithms.