Smoothed analysis of the low-rank approach for smooth semidefinite programs
Authors: Thomas Pumir, Samy Jelassi, Nicolas Boumal
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We present the empirical performance of the low-rank approach in the case of (Phase Cut). We compare it with a dedicated interior-point method (IPM) implemented by Helmberg et al. [1996] for real SDPs and adapted to phase retrieval as done by Waldspurger et al. [2015]. This adaptation involves splitting the real and the imaginary parts of the variables in (Phase Cut) and forming an equivalent real SDP with double the dimension. The Burer Monteiro approach (BM) is implemented in complex form directly using Manopt, a toolbox for optimization on manifolds [Boumal et al., 2014]. In particular, a Riemannian Trust-Region method (RTR) is used [Absil et al., 2007]. Theory supports that these methods can return an ASOSP in a finite number of iterations [Boumal et al., 2018a]. We stress that the SDP is not perturbed in these experiments: the role of the perturbation in the analysis is to understand why the low-rank approach is so successful in practice despite the existence of pathological cases. In practice, we do not expect to encounter pathological cases. Our numerical experiment setup is as follows. We seek to recover a signal of dimension d, z Cd, from n measurements encoded in the vector b Rn + such that b = |Az| + ϵ, where A Cn d is the sensing matrix and ϵ N(0, Id) is standard Gaussian noise. For the numerical experiments, we generate the vectors z as complex random vectors with i.i.d. standard Gaussian entries, and we randomly generate the complex sensing matrices A also with i.i.d. standard Gaussian entries. We do so for values of d ranging from 10 to 1000, and always for n = 10d (that is, there are 10 magnitude measurements per unknown complex coefficient, which is an oversampling factor of 5.) Lastly, we generate the measurement vectors b as described above and we cap its values from below at 0.01 in order to avoid small (or even negative) magnitude measurements. |
| Researcher Affiliation | Academia | Thomas Pumir ORFE Department Princeton University tpumir@princeton.edu Samy Jelassi ORFE Department Princeton University sjelassi@princeton.edu Nicolas Boumal Department of Mathematics Princeton University nboumal@math.princeton.edu |
| Pseudocode | No | The paper includes mathematical formulations, lemmas, and theorems but no pseudocode or algorithm blocks. |
| Open Source Code | No | The paper states: 'The Burer Monteiro approach (BM) is implemented in complex form directly using Manopt, a toolbox for optimization on manifolds [Boumal et al., 2014].' This refers to a third-party toolbox, not the authors' own source code for the described methodology or experiments. |
| Open Datasets | No | Our numerical experiment setup is as follows. We seek to recover a signal of dimension d, z Cd, from n measurements encoded in the vector b Rn + such that b = |Az| + ϵ, where A Cn d is the sensing matrix and ϵ N(0, Id) is standard Gaussian noise. For the numerical experiments, we generate the vectors z as complex random vectors with i.i.d. standard Gaussian entries, and we randomly generate the complex sensing matrices A also with i.i.d. standard Gaussian entries. We do so for values of d ranging from 10 to 1000, and always for n = 10d (that is, there are 10 magnitude measurements per unknown complex coefficient, which is an oversampling factor of 5.) Lastly, we generate the measurement vectors b as described above and we cap its values from below at 0.01 in order to avoid small (or even negative) magnitude measurements. The paper describes generating synthetic data for the experiments and does not mention using a publicly available dataset or providing access to their generated data. |
| Dataset Splits | No | The paper describes generating synthetic data for experiments but does not specify any training, validation, or test dataset splits or cross-validation methods. |
| Hardware Specification | No | The paper mentions that IPM ran into 'memory issues' for larger values of n, which implies hardware constraints, but it does not provide any specific hardware details such as CPU/GPU models, memory size, or other computing infrastructure used for the experiments. |
| Software Dependencies | No | The paper mentions using 'Manopt, a toolbox for optimization on manifolds' and an 'interior-point method (IPM) implemented by Helmberg et al. [1996]', but it does not provide specific version numbers for these or any other software dependencies. |
| Experiment Setup | Yes | Our numerical experiment setup is as follows. We seek to recover a signal of dimension d, z Cd, from n measurements encoded in the vector b Rn + such that b = |Az| + ϵ, where A Cn d is the sensing matrix and ϵ N(0, Id) is standard Gaussian noise. For the numerical experiments, we generate the vectors z as complex random vectors with i.i.d. standard Gaussian entries, and we randomly generate the complex sensing matrices A also with i.i.d. standard Gaussian entries. We do so for values of d ranging from 10 to 1000, and always for n = 10d (that is, there are 10 magnitude measurements per unknown complex coefficient, which is an oversampling factor of 5.) Lastly, we generate the measurement vectors b as described above and we cap its values from below at 0.01 in order to avoid small (or even negative) magnitude measurements. ... BM is run with k = n (rounded up)... |