PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal low-rank matrix recovery from Pauli measurements

Yi-Kai Liu

arXiv:1103.2816v2quant-phcs.ITmath.ITmath.STstat.MLstat.TH

TL;DR

Low-rank matrix recovery from Pauli measurements matters for quantum state tomography, but whether these structured measurements satisfy RIP was an open question. The paper uses Gaussian-process and entropy methods to establish universal recovery, with nearly optimal error bounds and a generalization to other suitable bases.

  • Problem

    The question is whether low-rank matrices can be recovered from structured Pauli measurements with universal guarantees, a problem relevant to quantum state tomography.

    Source: §1 · pp. 1–2

  • Method

    The paper proves RIP for random Pauli sampling using a Gaussian-process argument with Dudley’s entropy bound and covering-number estimates.

    Source: §1 · p. 2

  • Results

    A fixed set of O(rd poly log d) Pauli measurements supports recovery of all rank-r matrices, with nearly optimal noisy-error bounds for density-matrix reconstruction.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The result extends to incoherent orthonormal operator bases and informs tomography’s tradeoff between measurement settings and repetitions.

    Source: §1 · p. 2

    The bound in Proposition 2.4 is not universal: it concerns a random sampling operator likely to work for all matrices.

    Source: §2.2 · p. 6

Abstract

from arXiv · show

We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.

1 Introduction

The paper establishes universal low-rank recovery from Pauli measurements, addressing an open question about whether these structured measurements satisfy RIP. It connects the result to quantum state tomography and extends it to other incoherent orthonormal operator bases.

1 Introduction

  • Pauli measurements connect matrix recovery to Fourier compressed sensing and are experimentally convenient for quantum tomography because of the Pauli basis’s tensor-product structure.Low-rank density matrices model states that are nearly pure.Source: §1 · p. 1
  • A fixed universal set of O(rd poly log d) Pauli measurements enables recovery of every rank-r matrix, with RIP yielding nearly optimal noisy-error bounds.The paper also reports bounds for arbitrary matrices and for quantum states with a low-rank component plus a full-rank residual.Source: §1 · p. 2
  • In quantum state tomography, reconstruction error for a low-rank component is controlled by the full-rank residual, and arbitrary states admit an O(1/√r) Frobenius-norm error bound.The RIP also informs the tradeoff between measurement settings and repetitions per setting, which determine statistical noise.Source: §1 · p. 2
  • The result extends to orthonormal operator bases whose elements have small operator norm, and the RIP holds on a larger nuclear-norm-bounded matrix set.The paper describes the larger set as matrices X satisfying ∥X∥* ≤ √d.Source: §1 · p. 2
  • The proof uses a Gaussian process and Dudley’s entropy bound to account for correlations across low-rank matrices, then bounds nuclear-norm-ball covering numbers using entropy duality.This replaces a direct union-bound strategy that is insufficient for structured Pauli measurements.Source: §1 · pp. 2–3
  • A commuting set of Pauli measurements can reveal diagonal entries in its shared eigenbasis while leaving off-diagonal entries unknown, though random subsets are unlikely to all commute.This identifies a failure mode for particular measurement selections, not the typical random selection considered in the result.Source: §1 · p. 3

2 Our Results

The paper samples orthonormal-basis measurements and establishes a high-probability RIP for low-rank matrices, then applies it to universal recovery and quantum state tomography. The recovery bounds also describe how noise and the spectral tail affect reconstruction accuracy.

2.1 RIP for Pauli Measurements

  • With m = C K^2 rd log^6 d measurements, random sampling from an incoherent orthonormal basis satisfies RIP with high probability over matrices with ∥X∥*≤√r∥X∥F.The constant C depends on δ; the result extends beyond Pauli measurements to bases with small operator norm.Source: §2.1 · p. 4

2.2 Applications

  • Combining RIP with prior results gives universal low-rank recovery via the matrix Dantzig selector or matrix Lasso, with nearly optimal noisy-data accuracy bounds.Similar results hold for measurements in any incoherent operator basis.Source: §2.2 · p. 4
  • For quantum tomography, the target may be full-rank with decaying eigenvalues, and reconstruction aims to approximate it by retaining its leading singular values.The passage describes experimentally estimated Pauli measurements as noisy, with Gaussian noise approximating binomial noise when many experiments are averaged.Source: §2.2 · pp. 4–5
  • For noisy data, the Dantzig-selector error bound is universal—one sampling operator works for all matrices—and depends on noise strength and the residual tail.The bound's dependence on noise strength is nearly minimax-optimal.Source: §2.2 · p. 5
  • The Frobenius-tail bound is better when ∥Mc∥F ≪ ∥Mc∥*, as with slowly decaying eigenvalues or highly mixed tails.The log^6 d factor in this bound may not be tight.Source: §2.2 · p. 6
  • Proposition 2.4 is not universal: it guarantees likely success for a random sampling operator for each matrix, rather than one operator working for all matrices.It supplies a noisy-data Frobenius-error bound involving the residual tail.Source: §2.2 · p. 6

3 Proof of the RIP for Pauli Measurements

The proof establishes RIP by bounding the expected deviation and showing it concentrates, using Dudley’s inequality and covering-number bounds. The key technical estimates control Rademacher sums and the nuclear-norm ball’s covering numbers.

3.1 Overview

  • RIP reduces to showing ε_r(A) < 2δ − δ²; the overview bounds its expectation and then proves concentration around that mean.The concentration step uses an inequality for sums of independent symmetric random variables in a Banach space.Source: §3.1 · pp. 6–7

3.2 Proof of Lemma 3.1 (bounding a Rademacher sum in (r)-norm)

  • The quantity of interest is bounded by r · C4K log^(5/2) d log^(1/2) m, where C4 is a universal constant.The proof replaces the ±1 random variables with iid N(0, 1) Gaussian variables and applies Dudley’s inequality to the resulting Gaussian process.Source: §3.1 · p. 6, §3.2 · p. 7

3.1 Overview

  • The proof’s overview applies a Banach-space concentration inequality after bounding the expected deviation.The normed space is taken to be Banach for r ≥ 2, which the overview says suffices for its purposes.Source: §3.1 · pp. 6–7

3.3 Proof of Equation (21) (covering numbers of the nuclear-norm ball)

  • Entropy duality and Maurey’s empirical method bound the covering numbers needed for the nuclear-norm ball.The proof uses Schatten spaces with p = (log d)/(log d − 1) and q = log d rather than the nuclear and operator norm spaces directly.Source: §3.3 · p. 8

4 Outlook

The outlook identifies extensions and comparisons for low-rank recovery, while noting open questions in quantum state tomography.

4 Outlook

  • The authors ask whether their method extends to matrix completion or embeddings of low-dimensional manifolds into slightly higher-dimensional linear spaces.For matrix completion, they point to restricted strong convexity over non-spiky low-rank matrices; for manifold embeddings, they suggest generalizing sparse-vector RIP results.Source: §4 · p. 8
  • The paper leaves open how matrix Lasso compares with maximum likelihood estimation in low-rank quantum state tomography.Source: §4 · p. 8
  • Alternative tomography variants, including elementwise sparsity in a known basis, remain not fully explored.Source: §4 · p. 8

A.1 Overview

The appendix overview sets up an operator-space norm to measure deviation from the identity, then bounds its expectation and concentration to establish the RIP condition.

A.1 Overview

  • The proof targets ε_r(A) < 2δ − δ², a sufficient condition for RIP, by bounding ε_r(A)’s expectation and concentration.Source: §A.1 · p. 10
  • The proof defines a norm on self-adjoint operators and shows it makes the operator space a Banach space, using comparison with the Frobenius norm.The overview assumes r ≥ 2, which it says suffices for its purposes.Source: §A.1 · pp. 10–11
  • Symmetrization reduces the expected deviation to a Rademacher sum, whose (r)-norm is bounded for operators with uniformly bounded operator norm.The stated sum bound scales as C4 rK log^(5/2) d log^(1/2) m.Source: §A.1 · p. 11
  • A Banach-space concentration inequality for independent symmetric variables yields a failure probability that decreases exponentially in λ.The proof applies this after bounding the expectation of ε_r(A).Source: §A.1 · pp. 12–13

A.2 Proof of Lemma 3.1 (bounding a Rademacher sum in (r)-norm)

The lemma proof bounds a Rademacher sum by comparing it with a Gaussian process and controlling the process through covering numbers.

A.2 Proof of Lemma 3.1 (bounding a Rademacher sum in (r)-norm)

  • The proof replaces Rademacher variables with Gaussian variables and uses Dudley’s inequality to bound the expected supremum of the associated process.Source: §A.2 · p. 13
  • The Gaussian-process metric is upper-bounded by a norm-induced metric, allowing its covering numbers to be bounded using those of the corresponding unit ball.Source: §3.2 · p. 7, §A.2 · pp. 13–14
  • Covering numbers are controlled using a simple bound at small scales and an entropy-duality bound at large scales.The resulting estimate is C4 rK log^(5/2) d log^(1/2) m.Source: §A.2 · pp. 14–15

A.3 Proof of Equation (21) (covering numbers of the nuclear-norm ball)

The covering-number bound is applied through entropy duality, linking a dual covering number to the desired covering number. The argument uses Maurey’s empirical method and Schatten spaces chosen to avoid an infinite convexity constant.

A.3 Proof of Equation (21) (covering numbers of the nuclear-norm ball)

  • The covering-number result used here was introduced in, and the application follows the approach of [17].The proof states that this bound proves the claim.Source: §A.3 · pp. 15–16
  • The lemma applies when E has modulus of convexity of power type 2 and the vectors V_j in E* are uniformly bounded.It defines a norm on E and gives a covering-number bound with a universal constant C_2.Source: §A.3 · p. 15
  • Entropy duality relates the desired covering number to a dual covering number, with the two linked through inequalities for a map and its dual.The proof bounds the map’s covering number using Maurey’s empirical method.Source: §A.3 · p. 16
  • Choosing E = S_p with p = (log d)/(log d − 1) and E* = S_q with q = log d avoids the infinite λ(S_1) while retaining B_1 ⊆ B_p.The choice uses ∥M∥_p ≤ ∥M∥* and ∥M∥_q ≤ e∥M∥.Source: §A.3 · p. 16

B Proof of Proposition 2.4 (recovery of a full-rank matrix)

The proof combines the RIP-and-NNQ recovery bound with properties of Pauli sampling to establish Proposition 2.4. Its argument adapts the proof in [5] for Pauli rather than Gaussian measurements.

B Proof of Proposition 2.4 (recovery of a full-rank matrix)

Loading 1103.2816v2…