Universality in Learning from Linear Measurements

Babak Hassibi; Ehsan Abbasi; Fariborz Salehi

arxiv: 1906.08396 · v1 · pith:LCR2BQLUnew · submitted 2019-06-20 · 🧮 math.ST · stat.TH

Universality in Learning from Linear Measurements

Ehsan Abbasi , Fariborz Salehi , Babak Hassibi This is my paper

Pith reviewed 2026-05-25 19:44 UTC · model grok-4.3

classification 🧮 math.ST stat.TH

keywords universalitylinear measurementsconvex optimizationsignal recoveryphase retrievalquadratic measurementsGaussian reductionlow-rank recovery

0 comments

The pith

The minimum number of linear measurements needed for exact recovery depends only on the mean and covariance of the measurement vectors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that for convex optimization programs that recover structured signals from i.i.d. linear measurements, the smallest number of measurements guaranteeing perfect recovery with high probability is fixed once the mean vector and covariance matrix of the measurement distribution are fixed. This holds under mild conditions on the penalty and the distribution, so any distribution can be replaced by a Gaussian with the same first two moments without changing the recovery threshold. A reader cares because existing sharp results for Gaussian measurements then apply directly to many other sensing models. As a concrete payoff, the authors obtain an exact threshold of 3n measurements for phase retrieval via PhaseLift and 3nr for low-rank positive-semidefinite matrix recovery from quadratic measurements.

Core claim

Under mild conditions on the convex penalty f and on the distribution of the measurement vectors, the minimum number of measurements required for perfect recovery depends only on the first and second order statistics of the measurement vectors. Consequently the required number can be determined by studying the Gaussian case with the same mean and covariance, for which a rich theory already exists. The result is applied to random quadratic measurements, yielding that 3nr measurements suffice and are necessary to recover an n-dimensional rank-r positive-semidefinite matrix, which in turn settles that PhaseLift recovers a signal from 3n quadratic measurements.

What carries the argument

The universality reduction showing that recovery performance of a general i.i.d. measurement distribution equals that of the matching Gaussian distribution.

If this is right

Any distribution sharing the same mean and covariance as a Gaussian yields the identical recovery threshold for the same convex program.
The number of random quadratic measurements needed to recover a rank-r positive-semidefinite matrix is exactly 3nr.
PhaseLift recovers signals from exactly 3n quadratic measurements.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same reduction might apply to approximate recovery or noisy settings if the mild conditions can be verified there.
Designers could choose non-Gaussian measurements that match Gaussian performance while satisfying hardware constraints.
The result suggests testing whether other convex penalties outside the stated mild conditions still exhibit the same universality.

Load-bearing premise

The result requires unspecified mild conditions on the convex penalty and on the distribution of the measurement vectors to hold.

What would settle it

A concrete counter-example distribution and convex penalty satisfying the mild conditions for which the exact recovery threshold differs from the Gaussian with identical mean and covariance would falsify the claim.

Figures

Figures reproduced from arXiv: 1906.08396 by Babak Hassibi, Ehsan Abbasi, Fariborz Salehi.

**Figure 1.** Figure 1: Phase transition regimes for the estimator E{x0, A, R n , k · k`1 }, in terms of the oversampling ratio δ = m n and s = kx0k0 n , for the cases of (a) Gaussian measurements and (b) Bernoulli measurements and (c) χ 2 measurements. The blue lines indicate the theoretical estimate for the phase transition derived from Corollary 1. In the simulations we used vectors of size n = 256. The data is averaged over 1… view at source ↗

**Figure 2.** Figure 2: Phase transition regimes for both estimators 7 and (8), with f(X) = Tr(X), in terms of the oversampling ratio δ = m n and r = Rank(X0), for the cases of (a) estimator (7) with quadratic measurements and (b) estimator (8) with Gaussian measurements. In the simulations we used matrices of size n = 40. The data is averaged over 20 independent realization of the measurements. 4.1.1 Phase Transition of PhaseLif… view at source ↗

**Figure 3.** Figure 3: b compares the empirical result with the theoretical phase transition derived from Corollary 4 Each plot shows the norm of the error with respect to the sparsity of the matrix X0 and the ratio δ = m n2 . A comparison between the two plots indicates that the phase transitions of the two estimators (7) and (8) with f(X) = kXk`1 match. (a) (b) [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

read the original abstract

We study the problem of recovering a structured signal from independently and identically drawn linear measurements. A convex penalty function $f(\cdot)$ is considered which penalizes deviations from the desired structure, and signal recovery is performed by minimizing $f(\cdot)$ subject to the linear measurement constraints. The main question of interest is to determine the minimum number of measurements that is necessary and sufficient for the perfect recovery of the unknown signal with high probability. Our main result states that, under some mild conditions on $f(\cdot)$ and on the distribution from which the linear measurements are drawn, the minimum number of measurements required for perfect recovery depends only on the first and second order statistics of the measurement vectors. As a result, the required of number of measurements can be determining by studying measurement vectors that are Gaussian (and have the same mean vector and covariance matrix) for which a rich literature and comprehensive theory exists. As an application, we show that the minimum number of random quadratic measurements (also known as rank-one projections) required to recover a low rank positive semi-definite matrix is $3nr$, where $n$ is the dimension of the matrix and $r$ is its rank. As a consequence, we settle the long standing open question of determining the minimum number of measurements required for perfect signal recovery in phase retrieval using the celebrated PhaseLift algorithm, and show it to be $3n$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims a universality reduction letting you swap any i.i.d. linear measurements for Gaussians with matching mean and covariance, then applies it to get 3n for PhaseLift, but the conditions stay too vague to confirm the application works.

read the letter

The main takeaway is that under some mild conditions the minimal number of measurements for exact convex recovery depends only on the first two moments of the sensing vectors, so the threshold matches the Gaussian case with the same mean and covariance. They then use this to conclude that PhaseLift on rank-one quadratic measurements recovers a rank-r PSD matrix with 3nr measurements and therefore needs 3n for phase retrieval. That 3n number is the concrete claim that would matter to people working on phase retrieval. The reduction itself is the technical step that could be reused elsewhere if it holds. It lets existing Gaussian analyses carry over without re-proving everything from scratch for each new distribution. That is the part that could save time for readers who already know the Gaussian literature. The soft spot is exactly the one the abstract flags but does not resolve: the mild conditions on f and on the distribution are never written down. Without the precise statement it is impossible to check whether the rank-one projection ensemble satisfies them, so the 3n conclusion for PhaseLift remains conditional on unverified hypotheses. If those conditions turn out to be restrictive or fail for the quadratic model, the reduction does not apply and the claimed threshold does not follow. The paper is aimed at researchers who already work on sample-complexity bounds for structured convex recovery. Someone who wants a shortcut from non-Gaussian to Gaussian analyses would get the most out of it, but only after the conditions are checked in the full text. I would send it to referees. The open-question claim is specific enough that a careful review of the derivation and the applicability to quadratic measurements is worth the time rather than a desk reject.

Referee Report

2 major / 2 minor

Summary. The manuscript claims a universality result for the minimal number of i.i.d. linear measurements needed to exactly recover a structured signal by minimizing a convex penalty f subject to the measurement constraints. Under mild conditions on f and the measurement distribution, this number depends only on the mean vector and covariance matrix of the measurements, so it can be computed by reducing to an equivalent Gaussian ensemble. As an application, the authors conclude that 3nr random quadratic (rank-one projection) measurements suffice to recover an n×n rank-r positive semidefinite matrix, which implies that the PhaseLift algorithm recovers signals from 3n quadratic measurements in the phase-retrieval setting.

Significance. If the mild conditions can be stated precisely and verified for the quadratic-measurement model, the result would allow existing Gaussian compressed-sensing theory to be applied directly to a wider class of non-Gaussian ensembles that share the same first- and second-order statistics. The concrete 3n bound for PhaseLift would resolve a long-standing sample-complexity question for that algorithm.

major comments (2)

[Abstract / main theorem] Abstract (paragraph beginning 'Our main result states...') and the statement of the main theorem: the 'mild conditions' on f(·) and on the distribution of the measurement vectors are never enumerated. Because the universality claim is conditional on these hypotheses, their absence is load-bearing; without an explicit list it is impossible to check whether the rank-one projection distribution used in the PhaseLift application satisfies them.
[Application to quadratic measurements / PhaseLift] Application section (the derivation leading to the 3nr and 3n conclusions): no verification is supplied that the quadratic-measurement ensemble meets the (unspecified) mild conditions. If the conditions fail for this distribution, the reduction to the Gaussian case does not apply and the claimed sample complexities do not follow.

minor comments (2)

[Abstract] Abstract: 'the required of number of measurements' contains a typographical error and should read 'the required number of measurements'.
[Abstract] Abstract: 'can be determining by studying' should be 'can be determined by studying'.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for greater explicitness regarding the mild conditions and their verification. We will revise the manuscript to address both major comments.

read point-by-point responses

Referee: Abstract (paragraph beginning 'Our main result states...') and the statement of the main theorem: the 'mild conditions' on f(·) and on the distribution of the measurement vectors are never enumerated. Because the universality claim is conditional on these hypotheses, their absence is load-bearing; without an explicit list it is impossible to check whether the rank-one projection distribution used in the PhaseLift application satisfies them.

Authors: We agree that the conditions should be enumerated explicitly rather than referred to only as 'mild.' The full statement of Theorem 1 (Section 2) already lists them: f must be convex and continuous with a linear growth bound at infinity, and the measurement vectors must possess finite second moments with a positive-definite covariance matrix. To make this transparent, we will (i) replace the phrase 'some mild conditions' in the abstract with a concise bullet list of the hypotheses and (ii) restate the full list immediately before the theorem statement. This change will allow direct verification for any ensemble, including rank-one projections. revision: yes
Referee: Application section (the derivation leading to the 3nr and 3n conclusions): no verification is supplied that the quadratic-measurement ensemble meets the (unspecified) mild conditions. If the conditions fail for this distribution, the reduction to the Gaussian case does not apply and the claimed sample complexities do not follow.

Authors: We will insert a short verification subsection immediately after the statement of the 3nr bound. In it we confirm that the rank-one projection distribution (i) has zero mean, (ii) possesses a covariance matrix identical (up to scaling) to that of the standard Gaussian, and (iii) satisfies the finite-second-moment requirement. Because these properties match the hypotheses of Theorem 1 exactly, the reduction to the Gaussian case is justified and the sample-complexity conclusions follow. revision: yes

Circularity Check

0 steps flagged

No circularity; universality theorem reduces non-Gaussian case to Gaussian via new result

full rationale

The paper states a theorem that, under mild conditions on f and the measurement distribution, the recovery threshold depends only on first- and second-order statistics, permitting reduction to an equivalent Gaussian ensemble for which prior theory applies. This is a direct mathematical claim, not a self-definition, fitted-parameter prediction, or self-citation chain. The PhaseLift application (3nr / 3n) follows by invoking the theorem on the rank-one projection distribution and citing existing Gaussian results; no equation or step equates the output to the input by construction. The derivation is therefore self-contained against external Gaussian benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; the result rests on unspecified mild conditions on f and the measurement distribution. No free parameters, invented entities, or additional axioms are mentioned.

axioms (1)

domain assumption Mild conditions on the convex penalty f(·) and on the distribution of the linear measurements
Invoked in the abstract as prerequisite for the universality claim.

pith-pipeline@v0.9.0 · 5777 in / 1301 out tokens · 37074 ms · 2026-05-25T19:44:04.668800+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our main result states that, under some mild conditions on f(·) and on the distribution... the minimum number of measurements required for perfect recovery depends only on the first and second order statistics of the measurement vectors.
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the square of the Gaussian width indicates the phase transition

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 4 internal anchors

[1]

Living on the edge: Phase transitions in convex programs with random data

Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel A Tropp. Living on the edge: Phase transitions in convex programs with random data. Information and Inference: A Journal of the IMA, 3(3):224–294, 2014

work page 2014
[2]

Compressive wideband power spectrum estimation

Dyonisius Dony Ariananda and Geert Leus. Compressive wideband power spectrum estimation. IEEE Transactions on signal processing, 60(9):4775– 4789, 2012

work page 2012
[3]

Rop: Matrix recovery via rank-one projections

T Tony Cai, Anru Zhang, et al. Rop: Matrix recovery via rank-one projections. The Annals of Statistics, 43(1):102–138, 2015

work page 2015
[4]

The restricted isometry property and its implications for compressed sensing.Comptes rendus mathematique, 346(9-10):589–592, 2008

Emmanuel J Candes. The restricted isometry property and its implications for compressed sensing.Comptes rendus mathematique, 346(9-10):589–592, 2008

work page 2008
[5]

Exact matrix completion via convex optimization.Foundations of Computational mathematics, 9(6):717, 2009

Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization.Foundations of Computational mathematics, 9(6):717, 2009

work page 2009
[6]

Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements.Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59(8):1207–1223, 2006

work page 2006
[7]

Phaselift: Exact and stable signal recovery from magnitude measurements via con- vex programming

Emmanuel J Candes, Thomas Strohmer, and Vladislav Voroninski. Phaselift: Exact and stable signal recovery from magnitude measurements via con- vex programming. Communications on Pure and Applied Mathematics, 66(8):1241–1274, 2013

work page 2013
[8]

Latent variable graphical model selection via convex optimization

Venkat Chandrasekaran, Pablo A Parrilo, and Alan S Willsky. Latent variable graphical model selection via convex optimization. In2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1610–1613. IEEE, 2010

work page 2010
[9]

The convex geometry of linear inverse problems.Foundations of Computational mathematics, 12(6):805–849, 2012

Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems.Foundations of Computational mathematics, 12(6):805–849, 2012

work page 2012
[10]

Estimation of simultane- ously structured covariance matrices from quadratic measurements

Yuxin Chen, Yuejie Chi, and Andrea J Goldsmith. Estimation of simultane- ously structured covariance matrices from quadratic measurements. In2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7669–7673. IEEE, 2014

work page 2014
[11]

Exact and stable covariance estimation from quadratic sampling via convex programming

Yuxin Chen, Yuejie Chi, and Andrea J Goldsmith. Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Transactions on Information Theory, 61(7):4034–4059, 2015. 15

work page 2015
[12]

David Donoho and Jared Tanner. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing.Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1906):4273–4293, 2009

work page 1906
[13]

Compressed sensing.IEEE Transactions on infor- mation theory, 52(4):1289–1306, 2006

David L Donoho et al. Compressed sensing.IEEE Transactions on infor- mation theory, 52(4):1289–1306, 2006

work page 2006
[14]

Message-passing algorithms for compressed sensing.Proceedings of the National Academy of Sciences, 106(45):18914–18919, 2009

David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing.Proceedings of the National Academy of Sciences, 106(45):18914–18919, 2009

work page 2009
[15]

Operator norm consistent estimation of large- dimensional sparse covariance matrices.The Annals of Statistics, 36(6):2717– 2756, 2008

Noureddine El Karoui et al. Operator norm consistent estimation of large- dimensional sparse covariance matrices.The Annals of Statistics, 36(6):2717– 2756, 2008

work page 2008
[16]

Some inequalities for gaussian processes and applications

Yehoram Gordon. Some inequalities for gaussian processes and applications. Israel Journal of Mathematics, 50(4):265–289, 1985

work page 1985
[17]

On milman’s inequality and random subspaces which escape through a mesh in R n

Yehoram Gordon. On milman’s inequality and random subspaces which escape through a mesh in R n. InGeometric Aspects of Functional Analysis, pages 84–106. Springer, 1988

work page 1988
[18]

Sparse signal recovery from quadratic measurements via convex programming.SIAM Journal on Mathematical Analysis, 45(5):3019–3033, 2013

Xiaodong Li and Vladislav Voroninski. Sparse signal recovery from quadratic measurements via convex programming.SIAM Journal on Mathematical Analysis, 45(5):3019–3033, 2013

work page 2013
[19]

Low-rank positive semideﬁnite matrix recovery from corrupted rank-one measurements.IEEE Transactions on Signal Processing, 65(2):397–408, 2016

Yuanxin Li, Yue Sun, and Yuejie Chi. Low-rank positive semideﬁnite matrix recovery from corrupted rank-one measurements.IEEE Transactions on Signal Processing, 65(2):397–408, 2016

work page 2016
[20]

New Null Space Results and Recovery Thresholds for Matrix Rank Minimization

Samet Oymak and Babak Hassibi. New null space results and recovery thresholds for matrix rank minimization.arXiv preprint arXiv:1011.6326, 2010

work page internal anchor Pith review Pith/arXiv arXiv 2010
[21]

Simultaneously structured models with application to sparse and low-rank matrices

Samet Oymak, Amin Jalali, Maryam Fazel, Yonina C Eldar, and Babak Hassibi. Simultaneously structured models with application to sparse and low-rank matrices. IEEE Transactions on Information Theory, 61(5):2886– 2908, 2015

work page 2015
[22]

Universalitylawsforrandomizeddimension reduction, with applications.Information and Inference: A Journal of the IMA, 7(3):337–446, 2017

SametOymakandJoelATropp. Universalitylawsforrandomizeddimension reduction, with applications.Information and Inference: A Journal of the IMA, 7(3):337–446, 2017

work page 2017
[23]

A universal analysis of large-scale regularized least squares solutions

Ashkan Panahi and Babak Hassibi. A universal analysis of large-scale regularized least squares solutions. In Advances in Neural Information Processing Systems, pages 3381–3390, 2017. 16

work page 2017
[24]

Guaranteed minimum- rank solutions of linear matrix equations via nuclear norm minimization

Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum- rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471–501, 2010

work page 2010
[25]

Sparse reconstruction by convex relaxation: Fourier and gaussian measurements

Mark Rudelson and Roman Vershynin. Sparse reconstruction by convex relaxation: Fourier and gaussian measurements. In 2006 40th Annual Conference on Information Sciences and Systems, pages 207–212. IEEE, 2006

work page 2006
[26]

Gespar: Eﬃcient phase retrieval of sparse signals.IEEE transactions on signal processing, 62(4):928–938, 2014

Yoav Shechtman, Amir Beck, and Yonina C Eldar. Gespar: Eﬃcient phase retrieval of sparse signals.IEEE transactions on signal processing, 62(4):928–938, 2014

work page 2014
[27]

Variousthresholdsforl1-optimizationincompressedsensing

MihailoStojnic. Variousthresholdsforl1-optimizationincompressedsensing. 2009

work page 2009
[28]

Upper-bounding $\ell_1$-optimization weak thresholds

Mihailo Stojnic. Upper-bounding l1-optimization weak thresholds.arXiv preprint arXiv:1303.7289, 2013

work page internal anchor Pith review Pith/arXiv arXiv 2013
[29]

Precise error analysis of regularizedm-estimators in high dimensions.IEEE Transactions on Information Theory, 64(8):5592–5628, 2018

Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularizedm-estimators in high dimensions.IEEE Transactions on Information Theory, 64(8):5592–5628, 2018

work page 2018
[30]

Regularized linear regression: A precise analysis of the estimation error

Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. InConference on Learning Theory, pages 1683–1709, 2015

work page 2015
[31]

Regression shrinkage and selection via the lasso.Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996

Robert Tibshirani. Regression shrinkage and selection via the lasso.Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996

work page 1996
[32]

Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals

Joel A Tropp, Jason N Laska, Marco F Duarte, Justin K Romberg, and Richard G Baraniuk. Beyond nyquist: Eﬃcient sampling of sparse bandlim- ited signals. arXiv preprint arXiv:0902.0026, 2009

work page internal anchor Pith review Pith/arXiv arXiv 2009
[33]

The local convexity of solving systems of quadratic equations

Chris D White, Sujay Sanghavi, and Rachel Ward. The local convexity of solving systems of quadratic equations.arXiv preprint arXiv:1506.07868, 2015. 17 5 Simultaneously Sparse and Low-rank Matri- ces Another interesting example is where the unknown matrixX0⪰ 0 is simulta- neously sparse and low rank. To recoverX0, we would like to simultaneously minimize ...

work page internal anchor Pith review Pith/arXiv arXiv 2015
[34]

Consider the optimizations in (15)

Now, Pr{|ΦB− C| > 3δ} = Pr { g (ΦB− C δ ) > 2 } ≤ 1 2 E  g (ΦB− C δ ) ≤ 1 2 E  g (ΦA− C δ ) + 1 2 ⏐⏐⏐⏐E  g (ΦA− C δ ) − g (ΦB− C δ )⏐⏐⏐⏐ ≤ Pr{|ΦA− C| > δ} + 1 2 ⏐⏐⏐⏐E  g′(ζ)· (ΦA− C δ − ΦB− C δ )⏐⏐⏐⏐ ≤ Pr{|ΦA− C| > δ} + 1 δ|E [ΦA− ΦB]| n,m→∞ −−−−−→0 (20) Theorem 3. Consider the optimizations in (15). If A, B and f(.) satisfy Assumption 1 and 2, re...

work page

[1] [1]

Living on the edge: Phase transitions in convex programs with random data

Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel A Tropp. Living on the edge: Phase transitions in convex programs with random data. Information and Inference: A Journal of the IMA, 3(3):224–294, 2014

work page 2014

[2] [2]

Compressive wideband power spectrum estimation

Dyonisius Dony Ariananda and Geert Leus. Compressive wideband power spectrum estimation. IEEE Transactions on signal processing, 60(9):4775– 4789, 2012

work page 2012

[3] [3]

Rop: Matrix recovery via rank-one projections

T Tony Cai, Anru Zhang, et al. Rop: Matrix recovery via rank-one projections. The Annals of Statistics, 43(1):102–138, 2015

work page 2015

[4] [4]

The restricted isometry property and its implications for compressed sensing.Comptes rendus mathematique, 346(9-10):589–592, 2008

Emmanuel J Candes. The restricted isometry property and its implications for compressed sensing.Comptes rendus mathematique, 346(9-10):589–592, 2008

work page 2008

[5] [5]

Exact matrix completion via convex optimization.Foundations of Computational mathematics, 9(6):717, 2009

Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization.Foundations of Computational mathematics, 9(6):717, 2009

work page 2009

[6] [6]

Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements.Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59(8):1207–1223, 2006

work page 2006

[7] [7]

Phaselift: Exact and stable signal recovery from magnitude measurements via con- vex programming

Emmanuel J Candes, Thomas Strohmer, and Vladislav Voroninski. Phaselift: Exact and stable signal recovery from magnitude measurements via con- vex programming. Communications on Pure and Applied Mathematics, 66(8):1241–1274, 2013

work page 2013

[8] [8]

Latent variable graphical model selection via convex optimization

Venkat Chandrasekaran, Pablo A Parrilo, and Alan S Willsky. Latent variable graphical model selection via convex optimization. In2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1610–1613. IEEE, 2010

work page 2010

[9] [9]

The convex geometry of linear inverse problems.Foundations of Computational mathematics, 12(6):805–849, 2012

Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems.Foundations of Computational mathematics, 12(6):805–849, 2012

work page 2012

[10] [10]

Estimation of simultane- ously structured covariance matrices from quadratic measurements

Yuxin Chen, Yuejie Chi, and Andrea J Goldsmith. Estimation of simultane- ously structured covariance matrices from quadratic measurements. In2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7669–7673. IEEE, 2014

work page 2014

[11] [11]

Exact and stable covariance estimation from quadratic sampling via convex programming

Yuxin Chen, Yuejie Chi, and Andrea J Goldsmith. Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Transactions on Information Theory, 61(7):4034–4059, 2015. 15

work page 2015

[12] [12]

David Donoho and Jared Tanner. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing.Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1906):4273–4293, 2009

work page 1906

[13] [13]

Compressed sensing.IEEE Transactions on infor- mation theory, 52(4):1289–1306, 2006

David L Donoho et al. Compressed sensing.IEEE Transactions on infor- mation theory, 52(4):1289–1306, 2006

work page 2006

[14] [14]

Message-passing algorithms for compressed sensing.Proceedings of the National Academy of Sciences, 106(45):18914–18919, 2009

David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing.Proceedings of the National Academy of Sciences, 106(45):18914–18919, 2009

work page 2009

[15] [15]

Operator norm consistent estimation of large- dimensional sparse covariance matrices.The Annals of Statistics, 36(6):2717– 2756, 2008

Noureddine El Karoui et al. Operator norm consistent estimation of large- dimensional sparse covariance matrices.The Annals of Statistics, 36(6):2717– 2756, 2008

work page 2008

[16] [16]

Some inequalities for gaussian processes and applications

Yehoram Gordon. Some inequalities for gaussian processes and applications. Israel Journal of Mathematics, 50(4):265–289, 1985

work page 1985

[17] [17]

On milman’s inequality and random subspaces which escape through a mesh in R n

Yehoram Gordon. On milman’s inequality and random subspaces which escape through a mesh in R n. InGeometric Aspects of Functional Analysis, pages 84–106. Springer, 1988

work page 1988

[18] [18]

Sparse signal recovery from quadratic measurements via convex programming.SIAM Journal on Mathematical Analysis, 45(5):3019–3033, 2013

Xiaodong Li and Vladislav Voroninski. Sparse signal recovery from quadratic measurements via convex programming.SIAM Journal on Mathematical Analysis, 45(5):3019–3033, 2013

work page 2013

[19] [19]

Low-rank positive semideﬁnite matrix recovery from corrupted rank-one measurements.IEEE Transactions on Signal Processing, 65(2):397–408, 2016

Yuanxin Li, Yue Sun, and Yuejie Chi. Low-rank positive semideﬁnite matrix recovery from corrupted rank-one measurements.IEEE Transactions on Signal Processing, 65(2):397–408, 2016

work page 2016

[20] [20]

New Null Space Results and Recovery Thresholds for Matrix Rank Minimization

Samet Oymak and Babak Hassibi. New null space results and recovery thresholds for matrix rank minimization.arXiv preprint arXiv:1011.6326, 2010

work page internal anchor Pith review Pith/arXiv arXiv 2010

[21] [21]

Simultaneously structured models with application to sparse and low-rank matrices

Samet Oymak, Amin Jalali, Maryam Fazel, Yonina C Eldar, and Babak Hassibi. Simultaneously structured models with application to sparse and low-rank matrices. IEEE Transactions on Information Theory, 61(5):2886– 2908, 2015

work page 2015

[22] [22]

Universalitylawsforrandomizeddimension reduction, with applications.Information and Inference: A Journal of the IMA, 7(3):337–446, 2017

SametOymakandJoelATropp. Universalitylawsforrandomizeddimension reduction, with applications.Information and Inference: A Journal of the IMA, 7(3):337–446, 2017

work page 2017

[23] [23]

A universal analysis of large-scale regularized least squares solutions

Ashkan Panahi and Babak Hassibi. A universal analysis of large-scale regularized least squares solutions. In Advances in Neural Information Processing Systems, pages 3381–3390, 2017. 16

work page 2017

[24] [24]

Guaranteed minimum- rank solutions of linear matrix equations via nuclear norm minimization

Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum- rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471–501, 2010

work page 2010

[25] [25]

Sparse reconstruction by convex relaxation: Fourier and gaussian measurements

Mark Rudelson and Roman Vershynin. Sparse reconstruction by convex relaxation: Fourier and gaussian measurements. In 2006 40th Annual Conference on Information Sciences and Systems, pages 207–212. IEEE, 2006

work page 2006

[26] [26]

Gespar: Eﬃcient phase retrieval of sparse signals.IEEE transactions on signal processing, 62(4):928–938, 2014

Yoav Shechtman, Amir Beck, and Yonina C Eldar. Gespar: Eﬃcient phase retrieval of sparse signals.IEEE transactions on signal processing, 62(4):928–938, 2014

work page 2014

[27] [27]

Variousthresholdsforl1-optimizationincompressedsensing

MihailoStojnic. Variousthresholdsforl1-optimizationincompressedsensing. 2009

work page 2009

[28] [28]

Upper-bounding $\ell_1$-optimization weak thresholds

Mihailo Stojnic. Upper-bounding l1-optimization weak thresholds.arXiv preprint arXiv:1303.7289, 2013

work page internal anchor Pith review Pith/arXiv arXiv 2013

[29] [29]

Precise error analysis of regularizedm-estimators in high dimensions.IEEE Transactions on Information Theory, 64(8):5592–5628, 2018

Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularizedm-estimators in high dimensions.IEEE Transactions on Information Theory, 64(8):5592–5628, 2018

work page 2018

[30] [30]

Regularized linear regression: A precise analysis of the estimation error

Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. InConference on Learning Theory, pages 1683–1709, 2015

work page 2015

[31] [31]

Regression shrinkage and selection via the lasso.Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996

Robert Tibshirani. Regression shrinkage and selection via the lasso.Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996

work page 1996

[32] [32]

Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals

Joel A Tropp, Jason N Laska, Marco F Duarte, Justin K Romberg, and Richard G Baraniuk. Beyond nyquist: Eﬃcient sampling of sparse bandlim- ited signals. arXiv preprint arXiv:0902.0026, 2009

work page internal anchor Pith review Pith/arXiv arXiv 2009

[33] [33]

The local convexity of solving systems of quadratic equations

Chris D White, Sujay Sanghavi, and Rachel Ward. The local convexity of solving systems of quadratic equations.arXiv preprint arXiv:1506.07868, 2015. 17 5 Simultaneously Sparse and Low-rank Matri- ces Another interesting example is where the unknown matrixX0⪰ 0 is simulta- neously sparse and low rank. To recoverX0, we would like to simultaneously minimize ...

work page internal anchor Pith review Pith/arXiv arXiv 2015

[34] [34]

Consider the optimizations in (15)

Now, Pr{|ΦB− C| > 3δ} = Pr { g (ΦB− C δ ) > 2 } ≤ 1 2 E  g (ΦB− C δ ) ≤ 1 2 E  g (ΦA− C δ ) + 1 2 ⏐⏐⏐⏐E  g (ΦA− C δ ) − g (ΦB− C δ )⏐⏐⏐⏐ ≤ Pr{|ΦA− C| > δ} + 1 2 ⏐⏐⏐⏐E  g′(ζ)· (ΦA− C δ − ΦB− C δ )⏐⏐⏐⏐ ≤ Pr{|ΦA− C| > δ} + 1 δ|E [ΦA− ΦB]| n,m→∞ −−−−−→0 (20) Theorem 3. Consider the optimizations in (15). If A, B and f(.) satisfy Assumption 1 and 2, re...

work page