More Like this

1. DP-PCA: Statistically Optimal and Differentially Private PCA

   Xiyang Liu, Weihao Kong ( January 2022 , arXivorg)
2. The Kikuchi Hierarchy and Tensor PCA

   https://doi.org/10.1109/FOCS.2019.000-2  

   Wein, Alexander S. ; El Alaoui, Ahmed ; Moore, Cristopher ( November 2019 , 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS))

   For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the sumof-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (approximate message passing). Our level-ℓ algorithm can be thought of as a linearized message-passing algorithm that keeps track of ℓ-wise dependencies among the hidden variables. Specifically, our algorithms are spectral methods based on the Kikuchi Hessian, which generalizes the well-studied Bethe Hessian to the higher-order Kikuchi free energies. It is known that AMP, the flagship algorithm of statistical physics, has substantially worse performance than SOS for tensor PCA. In this work we ‘redeem’ the statistical physics approach by showing that our hierarchy gives a polynomial-time algorithm matching the performance of SOS. Our hierarchy also yields a continuum of subexponential-time algorithms, and we prove that these achieve the same (conjecturally optimal) tradeoff between runtime and statistical power as SOS. Our proofs are much simpler than prior work, and also apply to the related problem of refuting random k-XOR formulas. The results we present here apply to tensor PCA for tensors of all orders, and to k-XOR when k is even. Our methods suggest a new avenue for systematically obtaining optimal algorithms for Bayesian inference problems, and our results constitute a step toward unifying the statistical physics and sum-of-squares approaches to algorithm design. 

   more » « less
3. Evaluation of the robustness and accuracy of PCA-based algorithms for in-line Digital Holographic Microscopy

   https://doi.org/10.1364/3D.2023.JTu4A.35  

   Balachandran, K. ; Castaneda, R. ; Doblas, A. ( January 2023 , Optica Imaging Congress (3D, COSI, DH, FLatOptics, IS, pcAOP))

   This research undergraduate study evaluates the accuracy and robustness of a PCA-based phase reconstruction algorithm based on the number of phase-shifted images and the phase step for an in-line digital holographic microscope.

    

   more » « less
4. Bridging convex and nonconvex optimization in robust PCA: Noise, outliers and missing data

   https://doi.org/10.1214/21-AOS2066  

   Chen, Yuxin ; Fan, Jianqing ; Ma, Cong ; Yan, Yuling ( October 2021 , The Annals of Statistics)

   null (Ed.)
5. Realified L1-PCA for direction-of-arrival estimation: theory and algorithms

   https://doi.org/10.1186/s13634-019-0625-5  

   Markopoulos, Panos P. ; Tsagkarakis, Nicholas ; Pados, Dimitris A. ; Karystinos, George N. ( December 2019 , EURASIP Journal on Advances in Signal Processing)