Phaseless PCA: Low-Rank Matrix Recovery from Column-wise Phaseless Measurements
Authors: Seyedehsara Nayer, Praneeth Narayanamurthy, Namrata Vaswani
ICML 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our proposed algorithm for Ph-Co-LRMR, Alt Min Low Ra P, relies on three key ideas. The first is a clever spectral initialization for obtaining the first estimate of Span(U ). The second is the observation that, if U were known, we only need to solve q small (r-dimensional) standard PR problems to recover the b k s. Third, given an estimate of b k s, we can obtain a new improved estimate of Span(U ) by solving a least squares (LS) problem. The key insight that helps obtain a significant sample complexity reduction over standard PR is the observation that, for both the initialization and the update steps for U , conditioned on X , we have access to mq mutually independent measurements. These are not identically distributed, however, the right incoherence assumption on X ensures that the distributions are similar enough so that concentration holds with mq samples. Assuming constant condition number, our guarantee shows that the sample complexity, mq, for recovering a rank r matrix of size n q to ϵ accuracy is just Cnr5 log(1/ϵ). In the regime of small ranks r, this is close to the optimal complexity of 2nr. Ignoring log factors, when q n, this implies that only about r5 samples per signal are required. For small r, this is a significant improvement over standard PR approaches which necessarily require m Cn. Moreover, our guarantee for the dynamic setting (phaseless ST) shows that, if the subspace remains constant for a certain period of time before it changes, and if the largest principal angle of the change is not too small, we can both detect and track the changed subspace to within ϵ error with finite delay. This delay can be made small by increasing the number of measurements m per column. 2. Ph-Co-LRMR: Phaseless Column-wise Low-Rank Matrix Recovery |
| Researcher Affiliation | Academia | 1Department of Electrical and Computer Engineering, Iowa State University, USA. Correspondence to: Seyedehsara Nayer <sarana@iastate.edu>. |
| Pseudocode | Yes | Algorithm 1 Alt Min-Low Ra P: Alt-Min for Phaseless Low Rank Recovery; Algorithm 2 Phaseless ST |
| Open Source Code | No | The paper mentions 'For more video results, see (Nayer et al., 2019)' and 'proofs of the key lemmas can be found in (Nayer et al., 2019)' and 'The modified algorithm is presented in (Nayer et al., 2019)'. These refer to a preprint, but do not explicitly state that the code for the described methodology is released or available. |
| Open Datasets | No | The paper mentions using 'real videos' and 'mouse video' with 'simulated coded diffraction pattern (CDP) measurements' for evaluation. It also notes 'For the video results we consider the Coded Diffraction Pattern (CDP) measurements of the video. The details regarding the setup can be found in (Nayer et al., 2019)'. However, it does not provide specific access information (like a link, DOI, or formal citation with authors/year) for these datasets, nor does it refer to them as well-known, publicly available datasets. |
| Dataset Splits | No | The paper describes how the algorithm uses a 'new (independent) set of m measurements in each new update' and specifies 'α frame interval' for dynamic settings. However, it does not specify conventional training, validation, or test *dataset splits* (e.g., 80/10/10 percentages or sample counts) as is common for supervised learning tasks on a static dataset. The problem focuses on recovery from sequential measurements rather than partitioning a fixed dataset for training and evaluation. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments (e.g., GPU model, CPU type). |
| Software Dependencies | No | The paper mentions using 'reshaped Wirtinger flow (RWF) (Zhang et al., 2016)' as a component but does not specify any software names with version numbers for reproducibility (e.g., Python, PyTorch, TensorFlow versions, or specific library versions). |
| Experiment Setup | Yes | Theorem 2.1 (Guarantee for Alt Min Low Ra P). ...Set T := C log(1/ϵ), TRW F,t = C(log r + log κ2 + t(log(0.7)/ log(1 c))), and ω = 0.25σ min 2/q. Assume that, for the initialization step and for each new update, we use a new set of m measurements with m satisfying mq Cκ6µ2nr5 and m C max(r, log q, log n). Pick T = C log(1/ϵ). ... For this experiment we generate the data similarly as in the previous experiment and we use n = 300, r = 2, k1 = 2992, qfull = 6000, m = 100, α = 250 and consider two values of subspace change: SE(U 0, U 1) = 0.01, 0.8. |