Stable low-rank matrix recovery via null space properties

Introduction

In recent years, the recovery of objects (signals, images, matrices, quantum states etc.) from incomplete linear measurements has gained significant interest. While standard compressive sensing considers the reconstruction of (approximately) sparse vectors , we study extensions to the recovery of (approximately) low rank matrices from a small number of random measurements. This problem arises in a number of areas such as quantum tomography , signal processing , recommender systems and phaseless recovery . On the one hand, we consider both random measurement maps generated by independent random matrices with independent entries and on the other hand, measurements with respect to independent rank one measurements. We derive bounds for the number of required measurements in terms of the matrix dimensions and the rank of the matrix that guarantee successful recovery via nuclear norm minimization. Our results are uniform and stable with respect to noise on the measurements and with respect to passing to approximately rank-$r$ matrices. For rank-one measurements the latter stability result is new.

However, as we will see, the simpler least squares problem

works equally well or even better in terms of recovery under certain natural conditions. Apart from simplicity and computational efficiency it has the additional advantage that no estimate $\eta$ of the noise level is required. We note that other efficient recovery methods exist as well , but we will not go into details here.

where $\|A\|_{F}=\sqrt{\operatorname{tr}(A^{*}A)}$ denotes the Frobenius norm, $\operatorname{tr}$ being the trace. Note that

where the singular values $\sigma_{j}(X)$ are arranged in decreasing order and for $X$ with singular value decomposition $\sum_{j=1}^{n}\sigma_{j}(X)u_{j}v_{j}^{*}$ the matrix $X_{c}=\sum_{j=r+1}^{n}\sigma_{j}(X)u_{j}v_{j}^{*}$. The error estimate (8) means that reconstruction is robust with respect to noise on the measurements and stable with respect to passing to only approximately low rank matrices. These statements are uniform in the sense that they hold for all matrices $X$ simultaneously once the matrix $A$ has been drawn. They have been established in via the rank restricted isometry property (rank-RIP), see e.g. for the standard RIP and its implications.

While the RIP is a standard tool by now, recovery of low rank matrices via nuclear norm minimization is characterized by the so-called null space property , see below for details. By using this concept, we are able to significantly relax from subgaussian distributions of the entries to distributions with only four finite moments.

Fix $1\leq r\leq\min\{n_{1},n_{2}\}$ and $0<\rho<1$ and set

Here $c_{1},c_{2},c_{3}$ are positive constants that only depend on $C_{4}$.

In the special case, when $\Phi$ has independent standard Gaussian entries, we apply Gordon’s escape through a mesh theorem in order to obtain an explicit constant in the estimate for the number of measurements, see Theorem 19. Roughly speaking, with high probability, any $n_{1}\times n_{2}$ matrix of rank $r$ is stably recovered from $m>10r(n_{1}+n_{2})$ Gaussian measurements. We remark that the explicit bound $m>3r(n_{1}+n_{2})$ has been derived in , (see also and [4, Section 4.4] for a phase transition result in this context), but this bound considers nonuiform recovery, i.e. recovery of a fixed low rank matrix with a random draw of a Gaussian measurement matrix with high probability. Moreover, no stability under passing to approximately low rank matrices has been considered there. Our recovery result is therefore stronger than the one in , but requires more measurements.

2. Robust recovery of Hermitian matrices from rank-one projective measurements

Let us now focus on the particular case of recovering complex Hermitian $n\times n$ matrices from noisy measurements of the form (3), where the measurement matrices are proportional to rank-one projectors, i.e.,

The prior information that the desired matrix is Hermitian limits the search space in the convex optimization problem (4) and it simplifies to

Arguably, the most generic measurement matrices of the form (10) result from choosing each $a_{j}$ to be an independent complex standard Gaussian vector. For the particular case of phase retrieval — i.e., where the matrix of interest $X=xx^{*}$ is itself proportional to a rank-one projector — uniform recovery guarantees by means of (11) have been established for $m=Cn$ independent measurements in . Recently, this result has been generalized to recovery of any Hermitian rank $r$-matrix by means of $m=Crn$ such measurements in . Our refined analysis of the null space property enables us to further strengthen this result by additionally guaranteeing stability under passing to approximately low rank matrices:

Consider the measurement process described in (1) with $m$ measurement matrices of the form (10),where each $a_{i}$ is an independent complex standard Gaussian vector. Fix $r\leq n$, $0<\rho<1$ and suppose that

Here, $C_{1},C_{2}$ and $C_{3}$ denote positive universal constants. (In particular, for $\eta=0$ and $X$ of rank at most $r$ one has exact reconstruction.)

Let $r,\rho$ be as in Theorem 2 and suppose that each measurement matrix $A_{j}$ is of the form (10), where $a_{j}$, $j=1,\ldots,m$, are chosen independently from a (sufficiently accurate approximate) complex projective 4-design. If

then the assertions of Theorem 2 remains valid, possibly with different universal constants.

Note that Theorems 1, 2, 3 resp. Theorem 19 below and their proofs are presented in condensed versions in the conference papers resp. .

3. Recovery of positive semidefinite matrices reduces to a feasibility problem

Imposing additional structure on the matrices to be recovered can further strengthen low rank recovery guarantees. Positive semidefiniteness is one such structural prerequisite that, for instance, occurs naturally in the phase retrieval problem, quantum mechanics and kernel-based learning methods . Motivated by the former, Demanet and Hand pointed out that minimizing the nuclear norm — in the sense of algorithm (4) — can be superfluous for recovering positive semidefinite matrices of rank one. Instead, they propose to reduce the recovery algorithm to a mere feasibility problem and proved that such a reduction works w.h.p. for rank one projective measurements onto Gaussian vectors (the measurement scenario considered in Theorem 2). Subsequently, this recovery guarantee was strengthened by Candès and Li . Here, we go one step further and generalize these results to cover uniform and stable recovery of positive semidefinite matrices of arbitrary rank. Relying on ideas presented in , we establish the following statement. (We refer to Section 1.4 for the definition of the Schatten $p$-norm $\|\cdot\|_{p}$ used in (13).)

Fix $r\leq n$ and consider the measurement processes introduced in Theorem 2 (Gaussian vectors), or Theorem 3 (complex projective 4-designs), respectively. Assume that $m\geq C_{1}nr$ (in the Gaussian case) resp. $m\geq C_{2}snr\log n$ (in the design case), where $s\geq 1$ is arbitrary. Then, for $1\leq p\leq 2$ and any two positive semidefinite matrices $X,Z\in\mathcal{H}_{n}$,

Theorem 4 then in particular assures that the minimizer $Z^{\sharp}$ of this optimization program obeys

with high probability. Hence, recovering $X$ from noiseless measurements indeed reduces to a feasibility problem.

We emphasize that Theorem 4 is only established for rank one projective measurements. For the other measurement ensembles considered here — matrices with independent entries — one cannot expect such a statement to hold. This pessimistic prediction is due to negative results recently established in [63, Proposition 2]. Focusing on real matrices, the authors show that if the measurement matrices $A_{j}$ are chosen independently from a Gaussian orthogonal ensemble, then estimating any symmetric, positive semidefinite matrix $X$ via (14) becomes ill-posed, unless the number of measurements obeys

Finally, we want to point out that the fruitfulness of plain least squares regression for recovering positive semidefinite matrices was already pointed out and explored by Slawski, Li and Hein . However, there is a crucial difference in the mindset of and the results presented here. The main result [63, Theorem 2] of Slawski et al. assumes a fixed signal $X\succcurlyeq 0$ of interest and provides bounds for the reconstruction error in terms of geometric properties of both $X$ and the measurement ensemble. Conversely, Theorem 4 assumes fixed measurements (e.g. $m=Crn$ projectors onto Gaussian random vectors) and w.h.p. assures robust recovery of all matrices $X\succcurlyeq 0$ having approximately rank-$r$ simultaneously.

4. Notation

where $\sigma_{j}(Z)$, $j=1,\ldots,n$, denote the singular values of $Z$. It reduces to the nuclear norm $\|\cdot\|_{*}$ for $p=1$ and the Frobenius norm $\|\cdot\|_{F}$ for $p=2$. It is a common convention that the singular values of $Z$ are non-increasingly ordered. We write $Z=Z_{r}+Z_{c}$, where $Z_{r}$ is the best rank-$r$ approximation of $Z$ with respect to any Schatten $p$-norm of $Z$.

Applications

Note that such a “lift” allows for reinterpreting the phase-less sampling process as $\mathcal{A}(xx^{*})=b+w$. Also, the new object of interest $X:=xx^{*}$ is an Hermitian, positive semidefinite matrix of rank one. In turn, the measurement matrices $A_{i}=a_{i}a_{i}^{*}$ are constrained to be proportional to rank-one projectors. Consequently, such a “lift” turns the phase retrieval problem into a very particular instance of low rank matrix recovery — a fact that was first observed by Candès, Eldar, Strohmer and Voroninski . Subsequently, uniform recovery guarantees for $m=Cn$ complex standard Gaussian measurement vectors $a_{i}$ have been established which are stable towards additive noise. The main result in establishes with high probability that for any $X=xx^{*}$, solving the convex optimization problem (PhaseLift)

instead of PhaseLift. Our findings allow for establishing novel recovery guarantees for retrieving phases. Indeed, since (17) assures that any signal of interest is positive semidefinite and has precisely rank one, Theorem 4 is applicable and yields the following corollary.

The resulting minimizer $Z^{\sharp}$ of (20) obeys

and the rank-constraint manifests the problem’s non-convex nature. Hence, the convex optimization problem (20) can be viewed as a convex relaxation of (21), obtained by omitting the non-convex rank constraint.

2. Quantum information

In this section we describe implications and possible applications of our findings to problems in quantum information science. For the sake of being self-contained, we have included a brief introduction to crucial notions of quantum mechanics in the appendix. Quantum mechanics postulates that a finite $n$-dimensional quantum system is described by an Hermitian, positive semidefinite matrix $X$ with unit trace, called a density operator. This “quantum shape constraint” assures that all density operators meet the requirements of Theorem 4. Furthermore, the rank-one projective measurements assumed in that theorem can be recast as valid quantum mechanical measurements — see [43, Section 3] for possible implementations and further discussion on this topic. Note, however, that such a reinterpretation is in general not possible for the measurement matrices with independent entries considered in Theorem 1, because these matrices fail to be Hermitian. With Theorem 4 at hand, we underline its implications for two prominent issues in (finite dimensional) quantum mechanics.

Inferring a quantum mechanical description of a physical system is equivalent to assigning it a density operator (or quantum state) — a process referred to as quantum state tomography . Tomography is now a routine task for designing, testing and tuning qubits in the quest of building quantum information processing devices. Since the size of controllable quantum mechanical systems is ever increasingNowadays, experimentalists are able to create and control multi-partite systems of overall dimension $n=2^{8}$ in their laboratories . This results in a density operator of size $256\times 256$ (a priori $65\;536$ parameters). it is very desirable to exploit additional structure — if present — when performing such a task. One such structural property — often encountered in actual experiments — is approximate purity, i.e., the density operator $X$ is well approximated by a low rank matrix. Performing quantum state tomography under such a prior assumption therefore constitutes a particular instance of low rank matrix recovery .

The results presented in this paper provide recovery guarantees for tomography protocols that stably tolerate noisy measurements and moreover are robust towards the prior assumption of approximate purity. In the context of tomography, results of this type so far have already been established for $m=Cnr\log^{6}n$ random (generalized) Pauli measurements [47, Proposition 2.3] via proving a rank-RIP for such measurement matrices and then resorting to [15, Lemma 3.2]. However, this auxiliary result manifestly requires additive Gaussian noise and using a type of Dantzig, or Lasso selector to recover the best rank-$r$ approximation of a given density operator. This is not the case for the result established here, where performing a plain least squares regression of the form (14) is sufficient.

where $C_{1},C_{2},C_{3}$ and $C_{4}$ denote positive constants.

This statement is a direct consequence of Theorem 4. For the sake of clarity, we have re-scaled each projective measurement with $\sqrt{\frac{(n+1)n}{m}}$. This simplifies the resulting expression (23) and moreover facilitatesIn fact by resorting to the Frobenius norm bound in Theorem 4 (instead of the nuclear norm bound employed to arrive at Corollary 6), one obtains a performance guarantee that strongly resembles [47, Equation (8)] — the main recovery guarantee in that paper. direct comparison with the main result in , as it closely mimics the scaling employed there.

Corollary 6 is valid for any type of additive noise and no a priori knowledge of its magnitude is required. This includes the particularly relevant case of a Bernoulli error model — see e.g. [17, Section 2.2.2] and also — which is particularly relevant for tomography experiments. Also, note that the recovery error is bounded in nuclear norm, instead of Frobenius norm. Such a bound is very meaningful for tomography, since quantum mechanics is a probabilistic theory and the nuclear norm encapsulates total variational distance. Moreover, Helstrom’s theorem provides an operational interpretation of the nuclear norm distance bounded in (23): it is proportional to the maximal bias achievable in the task of distinguishing the two quantum states $X$ and $Z^{\sharp}$, provided that any physical measurement can be implemented.

Finally, note that the bound on the probability of failure in Corollary 6 is much stronger than the one provided in Theorem 4. Such a strengthening is possible, because the trace of any density operator equals one. We comment on this in Remark 34 below.

2.2. Distinguishing quantum states

One crucial prerequisite in the task of inferring density operators from measurement data, is the ability to faithfully distinguish any two density operators via quantum mechanical measurements. The most general notion of a quantum measurement is a positive operator valued measure (POVM) $\mathcal{M}=\left\{E_{m}:E_{m}\succcurlyeq 0,\sum_{m}E_{m}=\operatorname{id}\right\}$ [53, Chapter 2.2]. A POVM $\mathcal{M}$ is called informationally complete (IC) if for any two density operators $X\neq Z\in\mathcal{H}_{n}$ there exists $E_{m}\in\mathcal{M}\subseteq\mathcal{H}_{n}$ such that

This assures the possibility of discriminating any two quantum states via such a measurement in the absence of noise. Without additional restrictions, such an IC POVM must contain at least $n^{2}$ elements. However, such a lower bound can be too pessimistic, if the density operators of interest have additional structure. Approximate purity introduced in the previous subsection can serve as such an additional structural restriction:

For $r\leq n$, we call a POVM $\mathcal{M}=\left\{E_{m}\right\}_{m\in I}$ rank-$r$ restricted informationally complete (rank-$r$ IC), if (24) holds for any two density operators of rank at most $r$.

Bounds for the number $m$ of POVM elements required to assure rank-$r$-IC have been established in . These approaches exploit topological obstructions of embeddings for establishing lower bounds and explicit POVM constructions for upper bounds. For instance, in a particular rank-$r$-IC POVM containing $m=4r(n-r)-1$ elements is constructed.

Focusing less on establishing tight bounds and more on identifying entire families of rank-$r$ IC measurements, Kalev et al. observed that each measurement ensemble fulfilling the rank-RIP for some $r\leq n$ is also rank-$r$ IC. This in particular applies with high probability to $m=C\log^{6}n\;nr$ random (generalized) Pauli measurements . Theorem 4, and likewise Corollary 6, allow us to draw similar conclusions without having to rely on any rank-RIP. Indeed, in the absence of noise, these results guarantee for any rank-$r$ density operator $X$

with high probability. If this is the case, the measurement operator $\mathcal{A}$ allows for uniquely identifying any rank-$r$ density operator $X$. This in turn implies that $\mathcal{A}$ is rank-$r$ IC and the following corollary is immediate:

Fix $r\leq n$ arbitrary and let $C,C^{\prime}$ be absolute constants of sufficient size. Then

This statement is reminiscent of a conclusion drawn in : In the task of distinguishing quantum states, a POVM containing a 4-design essentially performs as good as as the uniform POVM (the union of all rank-one projectors).

The null space property for low-rank matrix recovery

The stability and robustness of (4) are established by the following theorem.

Theorem 11 can be deduced from the following stronger result.

The proof requires some auxiliary lemmas. We start with a matrix version of Stechkin’s bound.

This follows immediately from [26, Proposition 2.3], but for convenience we give the proof. Since the singular values of $M$ are non-increasingly ordered, it holds

where $\|\cdot\|$ is any unitarily invariant norm and $\Sigma(\cdot)$ denotes the diagonal matrix of singular values of its argument. Hence,

Applying the Frobenius robust null space property of $\mathcal{A}$ we obtain

By rearranging the terms in the above inequality we obtain

In order to bound $\|X-Z\|_{1}$ we use Hölder’s inequality, the Frobenius robust rank null space property of $\mathcal{A}$ and the inequality above,

Now we return to the proof of the theorem.

By Hölder’s inequality, Lemma 13 and the Frobenius robust rank null space property of $\mathcal{A}$

Substituting the result of Lemma 14 into (27) yields the desired inequality. ∎

It was first stated in that a slightly weaker property is actually equivalent to the successful recovery of $X$ via (28).

For the proof we refer to and [26, Chapter 4.6]. According to Lemma 14, another implication of the Frobenius robust rank null space property consists in the following error estimate in $\|\cdot\|_{1}$ for the case of noiseless measurements,

The above estimate remains true, if we require that for all $M\in\ker\mathcal{A}$, the singular values of $M$ satisfy

then $\mathcal{A}$ satisfies the Frobenius robust rank null space property of order $r$ with constants $\rho$ and $\tau$.

It is natural to expect that the recovery error gets smaller as the number of measurements increases. This can be taken into account by establishing the null space property for $\tau=\frac{\kappa}{\sqrt{m}}$. Then the error bound reads as follows

An important property of the set $T_{\rho,r}$ is that it is imbedded in a set with a simple structure. The next lemma relies on the ideas presented in for the compressed sensing setting.

where $\operatorname{conv}$ stands for the convex hull.

Then $D$ is the unit ball with respect to the norm

b To prove the embedding of $T_{\rho,r}$ into a scaled version of $D$, we estimate the norm of an arbitrary element $M$ of $T_{\rho,r}$. According to the definition of the $\|\cdot\|_{D}$-norm

and taking into account the inequality for the singular values of $M\in T_{\rho,r}$

Applying the last estimate to (34) we derive that

Set $a=\|M_{r}\|_{2}$. The maximum of the function

and is equal to $\sqrt{1+(1+\rho^{-1})^{2}}$. Thus for any $M\in T_{\rho,r}$ it holds

Employing the matrix representation of the measurement map $\mathcal{A}$, the problem of estimating the probability of the event (30) is reduced to the problem of giving a lower bound for the quantities of the form $\underset{x\in T}{\inf}\|Ax\|_{2}$. This is not an easy task for deterministic matrices, but the situation significantly changes for matrices chosen at random.

Gaussian measurements

Our main result for Gaussian measurements reads as follows.

where the last inequality follows from an estimate for the expectation of the largest singular value of a Gaussian matrix, see [26, Chapter 9.3]. ∎

Set $t:=\sqrt{2\ln(\varepsilon^{-1})}$. If $m$ satisfies (35), then

which means that with probability at least $1-\varepsilon$ map $\mathcal{A}$ satisfies the Frobenius robust rank null space property with constants $\rho$ and $\frac{\kappa\sqrt{2}}{\sqrt{m}}$. The error estimate follows from Theorem 11. ∎

Measurement matrices with independent entries and four finite moments

The $X_{ij}$ are independent random variables of mean zero,

Note that (by Hölder’s inequality) $C_{4}\geq 1$.

As before the idea of the proof is to show that the event (30) holds with high probability. In order to do so we apply Mendelson’s small ball method in the manner of .

where $h=\frac{1}{\sqrt{m}}\sum_{j=1}^{m}\varepsilon_{j}\phi_{j}$ with $(\varepsilon_{j})$ being a Rademacher sequence i.e., the $\varepsilon_{j}$ are independent and assume the values $1$ and $-1$ with probability $1/2$, respectively.. Then for any $\xi>0$ and any $t\geq 0$ with probability at least $1-e^{-2t^{2}}$

Assume that $Y$ has Frobenius norm one. The Payley-Zygmund inequality (see e.g. [26, Lemma 7.16], and also ), implies

Let $\Phi_{1},\ldots,\Phi_{m}$ be independent copies of a random matrix $\Phi$ as above. Let $\varepsilon_{1},\ldots,\varepsilon_{m}$ be independent Rademacher variables independent of everything else and let $H=\frac{1}{\sqrt{m}}\sum_{k=1}^{m}\varepsilon_{k}\Phi_{k}$. Then

Here $C_{1}$ is a constant that only depends on $C_{4}$.

Let $S=\sum_{k=1}^{m}\Phi_{k}$. We first desymmetrize the sum $H$ (see [45, Lemma 6.3]) and obtain

Let now $T_{\rho,r}$ and $D$ be the sets defined in Section 3, but restricted to the real-valued matrices. By Hölder’s inequality, for any $n_{1}\times n_{2}$ matrix $Y$ of Frobenius norm $1$ and rank at most $r$ and any $n_{1}\times n_{2}$ matrix $H$,

Let $H=\frac{1}{\sqrt{m}}\sum_{j=1}^{m}\varepsilon_{j}\Phi_{j}$ and let $\xi=\frac{1}{2\sqrt{2}}$ and $E=T_{\rho,r}$. Then it follows from Theorem 22 that for any $t\geq 0$ with probability at least $1-e^{-2t^{2}}$

Using Lemma 23 and the fact that all elements of $T_{\rho,r}$ have Frobenius norm $1$, we obtain

Combining now the fact that $T_{\rho,r}\subseteq\sqrt{1+(1+\rho^{-1})^{2}}D$ (see Lemma 17) with estimate (39) and Lemma 24 leads to

Using (40), (41) and (42) we see that choosing $m\geq c_{1}\rho^{-2}nr$ and $t=c_{4}m$ for suitable constants $c_{1},c_{4}$, we obtain with probability at least $1-e^{-c_{2}m}$

for suitable constants $c_{2},c_{3}$. Now the claim follows from Lemma 16 and Theorem 11 (both of which also hold in the real valued version by the same proofs respectively). ∎

Rank one Gaussian measurements

In this section we prove Theorem 2. The proof technique is an application of Mendelson’s small ball method analogous to the proof of Theorem 1. Let

Let $T_{\rho,r}$ be defined as $T^{\mathcal{H}}_{\rho,r}$ but with $\mathcal{H}_{n}$ replaced by the set of all complex $n\times n$-matrices (i.e. it is defined as before with $n_{1}=n_{2}=n$). Then $T^{\mathcal{H}}_{\rho,r}\subseteq T_{\rho,r}$. It is enough to show that with high probabiliy

We apply Theorem 22 with $E=T_{\rho,r}^{\mathcal{H}}$. The next lemma estimates the small ball probability $Q_{\frac{1}{\sqrt{2}}}(E;\phi)$ used in Mendelson’s method.

where the $\varepsilon_{j}$ form a Rademacher sequence. For any $M\in\mathcal{H}_{n}$ and any $n\times n$ matrix $Y$ of Frobenius norm $1$ and rank at most $r$

Since $E=T_{\rho,r}^{\mathcal{H}}\subseteq T_{\rho,r}\subseteq\sqrt{1+(1+\rho^{-1})^{2}}D$, this implies

Inspecting the above proof, resp. the proofs of the cited statements in , we see that the real valued analogue of Theorem 2 is also true. We even may assume for this that the $a_{j}$ are i.i.d. subgaussian with $k$-th moments, where $k\leq 8$, equal to the corresponding $k$-th moments of the Gaussian standard distribution. The constants then depend only on the distribution of the $a_{j}$. We also note that a similar statement in the real case for the recovery of positive semidefinite matrices using subgaussian measurements has been shown by Chen, Chi and Goldsmith in using the rank restricted isometry property.

Rank one measurements generated by 4-designs

Recall the definition of an approximate, weighted $t$-design.

We call a weighted set $\left\{p_{i},w_{i}\right\}_{i=1}^{N}$ of normalized vectors an approximate $t$-design of $p$-norm accuracy $\theta_{p}$, if

A set of unit vectors obeying $\theta_{p}=0$ for $1\leq p\leq\infty$ is called an exact $t$-design, see and also .

Let $\left\{p_{i},w_{i}\right\}_{i=1}^{N}$ be a an approximate $4$-design with either $\theta_{\infty}\leq 1/(16r^{2})$, or $\theta_{1}\leq 1/4$ that furthermore obeys $\left\|\sum_{i=1}^{N}p_{i}w_{i}w_{i}^{*}-\frac{1}{n}\operatorname{id}\right\|_{\infty}\leq\frac{1}{n}$. Suppose that the measurement operator $\mathcal{A}$ is generated by

Theorem 3 readily follows from combining this statement with Theorem 12.

is valid for all $\xi\in$. Now let $H=\sum_{i=1}^{m}\epsilon_{i}a_{i}a_{i}^{*}$ be as in Theorem 22. Lemma 17 together with the fact that $D$ is the convex hull of all matrices of rank at most $r$ and Frobenius norm 1 allows us to conclude for $m\geq 2n\log n$, that,

where the last bound is due to [43, Proposition 13]. Fixing $0<\xi<1/2$ arbitrarily and inserting these two bounds into Theorem 22 completes the proof.

An analogous statement for approximate 4-designs — with slightly worse absolute constants — can be obtained by resorting to the generalized versions of [43, Propositions 12 and 13] presented in Section 4.5.1 in loc. cit. which are valid for approximate 4-designs that satisfy the conditions stated in Theorem 28. ∎

The positive semidefinite case

Finally, we focus on the case, where the matrices of interest are Hermitian and positive semidefinite and establish Theorem 4. In order to arrive at such a statement, we closely follow the ideas presented in which in turn were inspired by containing an analogous statement for a non-negative compressed sensing scenario.

We require two further concepts from matrix analysis. For every positive semidefinite matrix $W\succcurlyeq 0$ with eigenvalue decomposition $W=\sum_{i=1}^{n}\lambda_{i}w_{i}w_{i}^{*}$ we define its square root to be $W^{1/2}:=\sum_{i=1}^{n}\sqrt{\lambda_{i}}w_{i}w_{i}^{*}$. In other words, $W^{1/2}$ is the unique positive semidefinite matrix which acts on the eigenspace corresponding to the eigenvalue $\lambda_{i}$ of $W$ by multiplication by $\sqrt{\lambda_{i}}$. Note that this matrix obeys $W^{1/2}\cdot W^{1/2}=W$. Also, recall that the condition number $\kappa(W)$ of a matrix $W$ is the ratio between its largest and smallest nonzero singular value. For an invertible Hermitian matrix with inverse $W^{-1}$ this number equals

of $\mathcal{H}_{n}$. Note that these definitions assure

see [7, p. 75]. Consequently, the mapping (48) preserves the rank of any matrix. The following result assures that the artificial measurement operator $\mathcal{A}_{W^{1/2}}$ obeys the Frobenius robust rank null space property, if the original $\mathcal{A}$ does.

This simple technical statement allows us to establish the main result of this section.

with constants $C=\frac{(1+\kappa(W)\rho)^{2}}{1-\kappa(W)\rho}$ and $D=\frac{3+\kappa(W)\rho}{1-\kappa(W)\rho}.$

Let $X,Z\succcurlyeq 0$ be arbitrary. Then

The desired statement follows from this estimate by taking into account (49) and (50). ∎

Note that in contrast to other recovery guarantees established here, Theorem 31 does not require any convex optimization procedure. However, it does require the measurement process to obey an additional criterion: the intersection of the span of measurement matrices with the cone of positive definite matrices must be non-empty. We show that this is the case for the rank-one projective measurements introduced in the previous section with high probability. Since it has already been established that sufficiently many measurements of this kind obey the Frobenius robust rank null space property with high probability (see Theorems 2 and 28 and their respective proofs), Theorem 4 can then be established by taking the union bound over the individual probabilities of failure.

Here, $C_{9},C_{10},C_{11}>0$ denote universal positive constants.

Also, by construction, $A$ is a random matrix with standard Gaussian entries. Essentially, this relation implies that $mW$ is Wishart-distributed. From (8) and the defining properties of eigen- and singular values we infer that

Alternatively, we could have relied on bounds on the condition number of Gaussian random matrices presented in . While these bounds would be slightly tighter, we feel that our derivation is more illustrative and it suffices for our purpose.

In order to show this statement, we are going to employ the matrix Bernstein inequalityResorting to the matrix Chernoff inequality would allow for establishing a similar result. However, in the case of an exact tight frame, the numerical constants obtained by doing so are slightly worse. [65, Theorem 6.1], see also , in order to establish

with high probability. Let $\lambda_{1}(W),\ldots,\lambda_{n}(W)$ denote the eigenvalues of $W$. Then such a bound together with the definition of the operator norm assures

This in turn implies $\lambda_{\min}(W)\geq 1/4$ as well as $\lambda_{\max}(W)\leq 3/4+\sqrt{\frac{n+1}{n}}\leq 2$ for $n\geq 2$ and the desired bound (57) readily follows.

via the triangle inequality and assumption (56) and along similar lines

readily follows for any $1\leq k\leq m$. The random matrices $M_{k}$ have mean-zero by construction and each of them obeys

These bounds allow us to set $R:=\frac{\sqrt{(n+1)n}}{m}$, $\sigma^{2}:=\frac{2\sqrt{(n+1)n}}{m}$ and apply the matrix Bernstein inequality ([65, Theorem 6.1], ) in order to establish

Finally, we are ready to prove Theorem 4.

We content ourselves with establishing the design case and point out that the Gaussian case can be proved analogously (albeit with different constants). Fix $0<\rho<1/8$ and suppose that

In Corollary 6 we focus on recovering density operators, i.e., positive semidefinite matrices $X$ with trace one. This trace constraint can be re-interpreted as an additional perfectly noiseless measurement

Corollary 6 then follows from combining this assertion with Theorem 28 and setting $p=1$.

MK, HR and UT acknowledge funding by the European Research Council through the Starting Grant StG 258926. The work of RK is supported by the Excellence Initiative of the German Federal and State Governments (Grants ZUK 43 & 81), the ARO under contracts W911NF-14-1-0098 and W911NF-14-1-0133 (Quantum Characterization, Verification, and Validation), the Freiburg Research Innovation Fund, the DFG (GRO 4334 & SPP1798), and the State Graduate Funding Program of Baden-Württemberg.

Appendix

For the sake of being self-contained we briefly recapitulate crucial concepts of (finite dimensional) quantum mechanics without going too much into detail. For further reading on the topics introduced here, we defer the interested reader to [53, Chapter 2.2].

An isolated quantum mechanical system is fully described by its density operator. For a finite $n$-dimensional quantum system, such a density operator corresponds to an Hermitian, positive semidefinite matrix $\rho$ with unit trace.

The most general notion of a measurement is that of a positive operator-valued measure (POVM). For an $n$-dimensional quantum system, a POVM corresponds to a collection $\mathcal{M}=\left\{E_{m}\right\}_{m\in I}$ of positive semidefinite $n\times n$ matrices that sum up to identity, i.e.,

The indices $m\in I$ indicate the possible measurement outcomes of performing such a POVM measurement. Upon performing $\mathcal{M}$ on a system described by $\rho$, quantum mechanics then postulates that the probability of obtaining the outcome (labeled by) $m$ corresponds to

Repeating the same measurement (i.e., preparing $\rho$ and measuring $\mathcal{M}$) many times allows one to estimate the $n$ probabilities $p(\lambda_{i},\rho)$ ever more accurately.

Note that the definitions of $\rho$ and $\mathcal{M}$ assure that ${p(m,\rho)}_{m\in I}$ is in fact a valid probability distribution. Indeed, $p(m,\rho)\geq 0$ follows from positive-semidefiniteness of both $\rho$ and $E_{m}$. Unit trace of $\rho$ assures proper normalization via

References