Phase Transitions in Sparse PCA
We study optimal estimation for sparse principal component analysis when the number of non-zero elements is small but on the same order as the dimension of the data. We employ approximate message passing (AMP) algorithm and its state evolution to analyze what is the information theoretically minimal mean-squared error and the one achieved by AMP in the limit of large sizes. For a special case of rank one and large enough density of non-zeros Deshpande and Montanari [1] proved that AMP is asymptotically optimal. We show that both for low density and for large rank the problem undergoes a series of phase transitions suggesting existence of a region of parameters where estimation is information theoretically possible, but AMP (and presumably every other polynomial algorithm) fails. The analysis of the large rank limit is particularly instructive.
Code (1)
Similar Papers 제목 키워드 기반
0-1 phase transitions in sparse spiked matrix estimation
We consider statistical models of estimation of a rank-one matrix (the spike) corrupted by an additive gaussian noise matrix in the sparse limit. In this limit the underlying hidden vector (that constructs the rank-one m…
Image RestorationObject CountingSemantic SegmentationWord Sense DisambiguationPhase Transitions in Frequency Agile Radar Using Compressed Sensing
FAR has improved anti-jamming performance over traditional pulse-Doppler radars under complex electromagnetic circumstances. To reconstruct the range-Doppler information in FAR, many compressed sensing (CS) methods inclu…
compressed sensingPhase transitions in the mini-batch size for sparse and dense two-layer neural networks
The use of mini-batches of data in training artificial neural networks is nowadays very common. Despite its broad usage, theories explaining quantitatively how large or small the optimal mini-batch size should be are mis…
Precise Phase Transition of Total Variation Minimization
Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex …
compressed sensingDenoisingPhaseMP: Robust 3D Pose Estimation via Phase-conditioned Human Motion Prior
We present a novel motion prior, called PhaseMP, modeling a probability distribution on pose transitions conditioned by a frequency domain feature extracted from a periodic autoencoder. The phase feature further enfo…
3D Pose EstimationMotion EstimationPose Estimation