Low rank matrix recovery from rank one measurements

Richard Kueng; Holger Rauhut; Ulrich Terstiege

Source-linked AI summary

Low rank matrix recovery from rank one measurements

Richard Kueng, Holger Rauhut, Ulrich Terstiege

arXiv:1410.6913v1Oct 25, 2014cs.ITmath.PRquant-ph

TL;DR

The paper studies uniform, stable recovery of Hermitian low-rank matrices from undersampled rank-one measurements, including phase retrieval as the rank-one case. It uses nuclear norm minimization with Gaussian vectors or approximate complex projective 4-designs and proves recovery with O(rn) or O(rn log n) measurements, respectively. The guarantees are robust to noise and are supported by a uniform bowling-scheme proof strategy.

Problem
The paper addresses recovery of Hermitian low-rank matrices from undersampled rank-one measurements, including the nonlinear phase-retrieval setting.
Method
The paper applies nuclear norm minimization and a uniform version of Tropp’s bowling scheme, using Mendelson–Koltchinskii lower-bound ideas for Gaussian and approximate 4-design measurements.
Results
The paper proves stable uniform recovery with O(rn) rank-one Gaussian measurements and O(rn log n) measurements drawn from weighted complex projective 4-designs.
Takeaways & Limitations
The guarantees cover all rank-r matrices simultaneously with high probability and remain valid under bounded additive measurement noise.
Takeaways & Limitations
The recovery analysis is geared toward nuclear norm minimization and does not provide guarantees for alternative algorithms; one approximate-design approach also uses coarse two-outcome measurements.

Abstract

from arXiv · show

We study the recovery of Hermitian low rank matrices $X \in \mathbb{C}^{n \times n}$ from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form $a_j a_j^*$ for some measurement vectors $a_1,...,a_m$, i.e., the measurements are given by $y_j = \mathrm{tr}(X a_j a_j^*)$. The case where the matrix $X=x x^*$ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements, $y_j = |\langle x,a_j\rangle|^2$ via the PhaseLift approach, which has been introduced recently. We derive bounds for the number $m$ of measurements that guarantee successful uniform recovery of Hermitian rank $r$ matrices, either for the vectors $a_j$, $j=1,...,m$, being chosen independently at random according to a standard Gaussian distribution, or $a_j$ being sampled independently from an (approximate) complex projective $t$-design with $t=4$. In the Gaussian case, we require $m \geq C r n$ measurements, while in the case of $4$-designs we need $m \geq Cr n \log(n)$. Our results are uniform in the sense that one random choice of the measurement vectors $a_j$ guarantees recovery of all rank $r$-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate $4$-designs generalizes and improves a recent bound on phase retrieval due to Gross, Kueng and Krahmer. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.

1. Introduction

Phase retrieval is a nonlinear inverse problem that becomes linear after lifting the signal to a rank-one matrix. The paper places this problem within low-rank recovery using Hermitian measurements and nuclear norm minimization, while highlighting difficulties caused by structured rank-one measurements.

The phase retrieval problem: Phase retrieval recovers a complex signal from quadratic, phase-insensitive measurements |⟨a_j, x⟩|^2 = b_j.The quadratic dependence makes the inverse problem nonlinear, and classical alternating-projection methods generally require extra constraints and parameter choices.
The phase retrieval problem: Lifting replaces the vector x with the outer product X = xx* so the measurements become linear in a rank-one matrix.This connects phase retrieval to low-rank matrix recovery, with both the unknown matrix and measurement matrices constrained by rank-one projectors.
Low rank matrix recovery: Low-rank matrix recovery reconstructs Hermitian matrices from incomplete linear measurements using convex programming based on nuclear norm minimization.The measurement model is b = A(X) + ϵ, and the nuclear-norm program is computationally efficiently solvable, although the paper does not provide guarantees for alternative algorithms.
Low rank matrix recovery: Random Gaussian measurement maps can recover rank-r matrices from considerably fewer than n^2 measurements, with uniform guarantees for all such matrices simultaneously.Earlier results use restricted isometry arguments, while nonuniform results for a fixed matrix require essentially m > 6rn measurements.
Structured measurements: Rank-one measurements are not generally incoherent enough for standard proof techniques, so phase retrieval requires specialized guarantees or non-optimal sampling rates.Structured measurement demands also motivate designs such as matrix completion and complex projective designs.
Weighted complex projective designs: A complex projective t-design makes discrete averages of polynomials of degree (t, t) match their uniform averages on the complex projective space.The paper introduces weighted designs using normalized vectors and nonnegative weights summing to one.

2. Main results

The paper establishes uniform, stable recovery guarantees for Hermitian low-rank matrices from rank-one Gaussian measurements and weighted complex projective 4-designs. Gaussian measurements require O(rn) samples, while 4-designs require O(nr log n), with extensions to real matrices and positive-semidefinite recovery.

Low rank matrix recovery from rank one Gaussian projections.: O(rn) rank-one Gaussian measurements guarantee uniform and stable recovery of rank-r matrices.The measurement matrices are proportional to projectors onto independent standard Gaussian vectors.
Low rank matrix recovery from rank one Gaussian projections.: η = 0 yields exact reconstruction in the Gaussian theorem, while positive noise permits error bounds under the stated measurement model.The constants in the Gaussian guarantee are universal.
Low rank matrix recovery from rank one Gaussian projections.: The Gaussian result extends prior rank-one recovery arguments to uniform recovery for arbitrary rank.The earlier comparison concerns a fixed positive-semidefinite rank-one matrix, whereas the present proof gives a simultaneous guarantee.
Recovery with 4-designs.: m ≥ C4nr log n measurements from a weighted complex projective 4-design guarantee stable uniform recovery of arbitrary Hermitian matrices of rank at most r.The vectors are sampled independently according to the design weights, and the guarantee includes noisy measurements.
Recovery with 4-designs.: Theorem 3 is close to optimal in design order: 2-designs cannot generally achieve sub-quadratic sampling without additional structure, while the 3-design case remains open.The 4-design result also covers proper 4-designs as a special case.
Recovery with 4-designs.: The Gaussian and 4-design guarantees differ only by a logarithmic factor, supporting complex projective designs as a derandomization tool.The paper also connects these results to related statements about distinguishing quantum states.
Variants and extensions.: Theorem 2 also holds for real standard Gaussian vectors and real symmetric matrices.The corresponding proof requires only similar adaptations.

3. Applications to quantum state tomography

Low-rank quantum state tomography uses convex recovery of density operators, with approximate 4-design measurements providing efficient implementations and recovery guarantees under stated accuracy and rank conditions.

Low-rank density operators model pure and almost-pure quantum systems, making quantum state tomography a low-rank matrix recovery problem.
Gaussian rank-one measurements are impractical for tomography because implementing their POVM elements requires O(poly(n)) elementary steps.
Sufficiently accurate approximate 4-designs preserve the recovery guarantee of Theorem 3, with operator-norm accuracy θ∞ ≤ 1/(16r^2) or trace-norm accuracy θ1 ≤ 1/4.The guarantee may hold with slightly worse absolute constants.
Approximate 4-design measurements can support efficient low-rank quantum state tomography and can, in principle, be implemented through realistic quantum setups.
One construction yields efficient POVM measurements with θ∞ = O(1/n^(1/3)) when the density-operator rank satisfies r ≤ C7n^(1/6).The rank restriction results from the construction’s limited accuracy.
Projected approximate-design vectors enable universal tomography using m = C4rn log n random measurements, provided the associated rank constraint holds.The projected vectors remain sub-normalized tight-frame vectors, and the measurement outcomes tr(ŵiŵi*ρ) are assumed known.
A second protocol reconstructs any rank-at-most-r density operator from m = ˜C4nr log n random measurements via the convex optimization problem (4).
The unitary-design-based protocol uses coarse two-outcome POVM measurements and does not exploit potentially available finer-grained output statistics.

4. Proofs

The proofs combine a uniform version of Tropp’s bowling scheme with Mendelson–Koltchinskii lower bounds to establish recovery for all low-rank matrices simultaneously. The Gaussian and 4-design arguments use analogous estimates, with the 4-design proof requiring m proportional to nr log n.

Proof strategy: The proof applies a uniform version of Tropp’s bowling scheme together with Mendelson–Koltchinskii bounds for restricted measurement quantities.The measurement map is represented by Φ(X)_i = tr(a_i a_i^* X), while the objective is the nuclear norm.
Robust recovery: Proposition 7 estimates convex-program recovery from noisy measurements through the minimum singular value of the measurement matrix on a descent cone.The subsequent random-matrix theorem supplies the needed estimate when Φ has independent identically distributed rows.
Uniform recovery: The uniform analysis replaces one fixed rank-r matrix with the union of all nonzero Hermitian matrices of rank at most r.This avoids ε-nets and yields a uniform success probability matching the non-uniform probability for a single fixed matrix.
Comparison and scope: The Gaussian proof’s alternative inexact-dual-certificate route appears to require measurement counts with substantially worse-than-linear dependence on r.The authors note that other dual-certificate constructions might recover linear scaling but would likely introduce more logarithmic factors.
4-design measurements: For complex projective 4-designs, suitable bounds for Q^2_ξ and E∥H∥∞ yield the result when m = C_4 n r log n.The proof follows the Gaussian case after applying Theorem 8 and choosing constants depending on ξ.

5. Appendix

The appendix develops multilinear-algebra tools for tensor spaces, partial traces, symmetric subspaces, and approximate designs. It proves that approximate t-designs remain approximate k-designs for every lower order k.

Norms and concentration: The appendix reviews Schatten norms, matrix Hölder’s inequality, and a matrix Chernoff inequality used in the analysis.These tools support norm comparisons and concentration bounds for sums of independent positive definite matrices.
Tensor-space framework: Tensor products identify matrices with elements of M_n and provide the setting for partial traces and transpositions.The appendix explains tensor products, contractions, and permutation actions through multilinear algebra and wiring calculus.
Tensor operations: Partial traces preserve positive semidefiniteness, while the nuclear norm is multiplicative over tensor products.The appendix also states the analogous multiplicativity for the operator norm.
Symmetric tensors: The symmetrizer projects tensor powers onto the totally symmetric subspace, whose dimension is given in the appendix.The construction averages over permutations in the symmetric group.
Approximate designs: Every approximate t-design in operator or trace norm is also an approximate k-design with the same accuracy for 1 ≤ k ≤ t.The proof uses partial traces, positive semidefinite ordering, and nuclear-norm monotonicity.
Approximate designs: The appendix supplies an alternative multilinear-algebra proof of the lower-order design property rather than relying only on the equivalent polynomial characterization.The operator-norm and trace-norm cases are handled through partial-trace arguments.