Recovering low-rank matrices from few coefficients in any basis

I Introduction

We consider the problem of efficiently recovering a low-rank matrix from a small number of expansion coefficients with respect to some basis in the space of matrices. Related questions have recently enjoyed a substantial amount of attention (c.f. for a highly incomplete list of references).

To get some intuition for the problem, note that one needs roughly $rn$ parameters to specify an $n\times n$-matrix $\rho$ of rank $r$. Therefore, it might be surmised that about the same number of expansion coefficients of $\rho$ (with respect to some fixed matrix basis) are sufficient to uniquely specify $\rho$ within the set of low-rank matrices. It is by far less clear whether $\rho$ can be recovered from this limited set of coefficients in a computationally tractable way.

Low-rank matrix recovery may be compared to a technique studied under the name of compressed sensing . In its simplest version, the task there is to recover a sparse vector from few Fourier coefficients. Informally, the property of having a low rank is the “non-commutative analogue” of sparsity. In this sense, one may think of the matrix recovery problem as a non-commutative version of compressed sensing.

This field of research was started in earnest with the results in . There, it was shown that surprisingly, reconstructing a rank-$r$ matrix from only $O(nr\operatorname{polylog(n)})$ randomly selected matrix elements can be done efficiently employing a simple convex optimization algorithm. These findings were partly inspired by methods used earlier in compressed sensing .

The results presented in were as spectacular as they were difficult to prove; the tighter bounds in required dozens of pages. At the same time, the proof techniques seemed to be tailored to the fact that matrix elements, as opposed to more general expansion coefficients, had been sampled.

In the present author and collaborators developed new methods for analyzing low-rank matrix recovery problems. The work was motivated by the desire to prove analogues of applicable to certain problems in quantum mechanics. Three main improvements were achieved. Most importantly, the mathematical effort for obtaining near-optimal bounds on the number of coefficients needed to determine a low-rank matrix was cut dramatically, with a condensed (but complete) version of the proof fitting on a single page. Also, the new arguments depend much less on the specific properties of the basis used. Lastly, in some situations, the bounds obtained are tighter than those presented previously. In some cases, the gap between lower and upper bounds is reduced to a multiplicative constant.

The present paper builds on the methods of . It aims to make them accessible to readers not accustomed to the language of quantum information theory, supplies many details missing in due to space limitations, generalizes the results to arbitrary operator bases, and provides tighter estimates.

Throughout the main part of this paper the word “matrix” will be used to mean “Hermitian matrix” (or, equivalently, “symmetric matrix”, if one prefers to work over the real numbers). Our methods work more naturally in this setting, and a lack of Hermiticity would just be a technical problem obscuring the essence of the argument. In fact little generality is lost. In Section III-D, we describe a straight-forward way for translating any non-Hermitian matrix recovery problem to a Hermitian one. Therefore, in essence, all our results include this more general case.

The unknown rank-$r$ matrix to be recovered will be denoted by $\rho$. On the space of Hermitian matrices, we use the Hilbert-Schmidt inner product $(\sigma_{1},\sigma_{2})=\tr(\sigma_{1}^{\dagger}\sigma_{2})$. We assume that some ortho-normal basis $\{w_{a}\}_{a=1}^{n^{2}}$ with respect to this inner product has been chosen (referred to as an operator basis). Thus, $\rho$ can be expanded as

The question addressed below is: given that $\rank\rho\leq r$, how many randomly chosen coefficients $(w_{a},\rho)$ do we need to know, before we can efficiently reconstruct $\rho$?

In order to perform the reconstruction, we will utilize the algorithm employed in . Let $\Omega\subset[1,n^{2}]$ be a random set of size $m$. Assume that we know the coefficients $(w_{a},\rho)$ for all $a\in\Omega$. The algorithm simply consists of performing the following (efficiently implementable) convex optimization over the space of matrices:

Above, $\|\sigma\|_{1}$ is the trace-norm (also Schatten 1-norm or nuclear norm), i.e. the sum of the singular values of $\sigma$. Let $\sigma^{\star}$ be a solution of the optimization. Theorem 3 quantifies the probability (with respect to the sampling process) of $\sigma^{\star}$ being unique and equal to $\rho$, as a function of the the number $m$ of coefficients revealed.

It is clear that the algorithm will perform poorly if $\rho$ has very few non-zero expansion coefficients with respect to the basis $\{w_{a}\}$ . To avoid such a situation, we must ensure that a typical coefficient will contain “enough non-trivial information” about $\rho$. That is the content of the various notions of “incoherence” which have been proposed . Our definition of incoherence is stated below. It is closely related to, but more general than, the parameter $\mu$ used in . In particular, going beyond previously published situations, we find that there are certain bases with the property that any low-rank matrix is incoherent with respect to them.

To state the results more precisely, we need to introduce some notation. (We try to follow as closely as possible). Let $U=\range\rho$ be the row space of $\rho$ (which is equal to its column space, due to Hermiticity). Let $P_{U}$ be the orthogonal projection onto $U$. The space of matrices

projects We will use calligraphic $\mathcal{P}$’s for matrix-valued projections, and roman $P$’s for vector-valued projections. onto $T$. Whenever there is little danger of confusion, we will not make the dependency of $T,\mathcal{P}_{T}$ and other objects on $\rho$ explicit in our notation.

Recall the definition of the sign function: $\sign(x)=x/|x|$ for $x\neq 0$ and $\sign(0)=0$. Below, we will apply the sign function (and other real functions) to Hermitian matrices. Expressions like $\sign\sigma$ are to be understood in terms of the usual “functional calculus”. I.e. $\sign\sigma$ is the matrix which is diagonal in the same basis as $\sigma$, but with eigenvalues $\sign(\lambda_{i})$, where the $\lambda_{i}$ are the eigenvalues of $\sigma$.

The unadorned norm $\|\sigma\|$ of a matrix $\sigma$ refers to the operator norm (or spectral norm): the largest singular value. The 2-norm (also Frobenius norm) is $\|\sigma\|_{2}=\tr(\sigma\sigma)^{1/2}$.

We can now state our definition of coherence.

The $n\times n$-matrix $\rho$ has coherence $\nu$ with respect to an operator basis $\{w_{a}\}_{a=1}^{n^{2}}$ if either

Let $\rho$ be a rank-$r$ matrix with coherence $\nu$ with respect to the standard operator basis. Let $\Omega\subset[1,n^{2}]$ be a random set of size $|\Omega|\geq O(nr\nu^{4}\ln^{2}n)$. Then the solution $\sigma^{\star}$ of the optimization problem (1) is unique and equal to $\rho$ with probability at least $1-n^{-3}$.

Our main theorem works for arbitrary operator bases, improves the $\nu$-dependency and will turn out to be easier to prove.

Let $\rho$ be a rank-$r$ matrix with coherence $\nu$ with respect to an operator basis $\{w_{a}\}_{a=1}^{n^{2}}$. Let $\Omega\subset[1,n^{2}]$ be a random set of size $|\Omega|\geq O(nr\nu(1+\beta)\ln^{2}n)$. Then the solution $\sigma^{\star}$ of the optimization problem (1) is unique and equal to $\rho$ with probability at least $1-n^{-\beta}$.

The precise condition on $|\Omega|$ for the statement in Theorem 3 to hold is

(No attempt has been made to optimize the constants appearing in this expression.) In the expositional part of this paper, we will frequently employ the ‘‘big-Oh’’-notation We write $|\Omega|\geq O(f(n,r,\nu,\beta))$ if there is a constant $C$ such that for $n$ large enough and for all $\nu,\beta$ and $r\leq n$, it holds that $|\Omega|\geq Cf(n,r,\nu,\beta)$. to give simplified accounts of otherwise complex expressions. However, in the more technical sections, it will be shown that all statements hold for any finite $n$ (and not just asymptotically, as the $O$-notation might suggest) and all constants will be worked out explicitly.

We remark that the only property of the basis $\{w_{a}\}$ itself that has entered the discussion so far is its operator norm $\max_{a}\|w_{a}\|$. Intuitively, the reason is easily understood: matrices with small operator norm are “incoherent” to all low-rank matrices simultaneously. More precisely: if $\rho$ is a matrix of rank $r$, normalized such that $\|\rho\|_{2}=1$, then Hölder’s inequality for matrices [12, Corollary IV.2.6] gives the estimate

for any matrix $w$. Hence the squared overlap on the left hand side is small if both $r$ and $\|w\|$ are. As a corollary, we can actually derive (4) from (3). Indeed

(having used the simple fact that $\max_{\sigma\in T}(\rank\sigma)=2r$).

Equation (6) has a well-known analogue in compressed sensing . There, one uses the fact that “vectors with small entries” are incoherent to “sparse vectors”. Indeed, if $\sigma_{1},\sigma_{2}$ are vectors, $\|\sigma_{1}\|$ is taken to be the supremum norm (i.e. the absolute value of the largest component of $\sigma_{1}$) and $\rank\sigma_{2}$ is the number of non-zero entries of $\sigma_{2}$, then Eq. (6) remains true. The best-known example of a basis consisting of vectors with small supremum norm is the Fourier basis. Motivated by this analogy, we will refer to operator bases fulfilling (3) as Fourier-type bases. Arguably, from a mathematical point of view, they form the most natural setting for low-rank matrix recovery To the best knowledge of the author, the first researcher who clearly appreciated the significance of the basis’ operator norm was Y.-K. Liu. He proved that some of the bounds in continue to hold for all low-rank matrices, if – instead of matrix elements – one samples expansion coefficients with respect to a certain unitary operator basis . .

We will prove Theorem 3 for Fourier-type bases first and then present two relatively simple modifications which allow us to cover the general case.

In later sections we will refine the analysis for Fourier-type bases, arriving at Theorem 4. Asymptotically, the estimate is tight up to multiplicative constants.

Let $\rho$ be a rank-$r$ matrix and suppose that $\{w_{a}\}$ is an operator basis fulfilling $\max_{a}\|w_{a}\|^{2}\leq\frac{\nu}{n}$. Let $\Omega\subset[1,n^{2}]$ be a random set. Then the solution $\sigma^{\star}$ to the optimization problem (1) is unique and equal to $\rho$ with probability of failure smaller than $e^{-\beta}$, provided that

Comparable bounds were known before in situations where the operator basis itself was drawn randomly (as opposed to a random subset from any given basis) or under additional assumptions on the spectrum of $\rho$ . However, this seems to be the first time the optimal $\log$-factor in the bound on $|\Omega|$ has been proven to be achievable in a matrix recovery problem, where the involved basis and unknown matrix were neither randomized nor subject to constraints beyond their rank.

I-B Examples

Because we work in the setting of Hermitian matrices, it holds that

so that every time one matrix element is revealed, we additionally obtain knowledge of the transposed one. Accordingly, the Hermitian analogue of sampling matrix elements is sampling expansion coefficients with respect to the basis $\{w_{a}\}$ of matrices of the form

for $i<j$, together with the matrices $e_{i}e_{i}^{\dagger}$ supported on the main diagonal.

Thus, Theorem 3 is applicable with $\nu=\max\{\mu_{1},2\mu_{2}^{2}\}$.

I-B2 Unitary operator bases

We briefly comment on bases with minimal operator norm. Let $\{w_{a}\}$ be an ortho-normal basis in the space of matrices. At this point, we do not assume that the basis is Hermitian. Denote the singular values of $w_{a}$ by $s_{i}(w_{a})$. Since

it follows that $\|w_{a}\|^{2}=\max_{i}s_{i}^{2}(w_{a})\geq\frac{1}{n}$. Therefore $\nu=1$ is the best possible value in (3). It is achieved exactly if $\sqrt{n}\,w_{a}$ is unitary for every $a\in[1,n^{2}]$. Such unitary operator bases have been studied in some detail (see e.g. ).

A standard example with manifold applications is the Pauli (operator) basis. For $n=2$ it is given by $w_{a}=\frac{1}{\sqrt{2}}\sigma_{a}$, where

The bases $\{w_{a}^{(k)}\}$ possess an exceedingly rich structure which is at the heart of many central results in quantum information theory (see e.g. ; for a brief introduction see ). We will make use of the existing theory to prove lower bounds on $|\Omega|$ in Section III-C.

The Pauli basis is a commonly used ingredient in experimental quantum-state tomography—a fact which initially motivated this work.

I-C Intuition

The basic intuition underlying our results differs little from previous approaches . For the sake of being self-contained, we still give a brief non-technical account of some aspects we find essential. (Technical differences to existing publications are outlined in the next section.)

Consider the sketch in Fig. 1(a) (partly inspired by ). The matrix $\rho$ is an element of an $n^{2}$-dimensional linear space. The axis labeled $\Omega$ in the diagram represents the roughly $O(rn)$ coordinates we have information about, i.e. the space spanned by the $\{w_{a}\,|\,a\in\Omega\}$. As the $n^{2}-O(rn)$ remaining coordinates (denoted by $\Omega^{\bot}$) are unknown, there is a large affine space of matrices compatible with the available information. We have to specify an algorithm which picks one point from this high-dimensional affine space, and prove that our choice is identical to $\rho$ with high probability.

Since we are looking for a low-rank object, it would be natural to choose the lowest-rank matrix in the affine space of all matrices compatible with the information we have. However, minimizing the rank over an affine space is in general NP-hard . To get around this problem, we employ the trace heuristic, which stipulates that minimizing the trace-norm is a good proxy for rank minimization (see e.g. ). The resulting optimization problem (1) is an efficiently solvable semi-definite program.

The objective thus becomes proving that the trace-norm restricted to the affine plane has a strict and global minimum at $\rho$ (Fig. 1(b)). Thus, if $\rho+\Delta\neq\rho$ is any matrix in the affine plane, we need to show that

A short handwaving argument indicates that adding a generic deviation $\Delta$ to a low-rank $\rho$ is indeed likely to increase the trace-norm.

To see why, recall that the trace-norm of a matrix is larger than the sum of the absolute values of the elements on the main diagonal . We will apply this estimate to $\rho+\Delta$ expressed in some eigenbasis of $\rho$. Let $\rho_{1},\dots,\rho_{r}$ be the eigenvalues of $\rho$. Then

For generic deviations $\Delta$, we expect that the $\Delta_{i,i}$ all have comparable magnitudes. Therefore, as long as $r\ll n$, the second sum in (11) will dominate the first one as required.

The “only” difficulty faced in this paper consists in proving that $\|\rho+\Delta\|_{1}>\|\rho\|_{1}$ holds not just for generic matrices $\rho+\Delta$ in the aforementioned affine plane, but for all such elements simultaneously. Key to that will be a simple concept from convex optimization theory: a dual certificate . By that we mean a matrix $Y$ such that

for $\Delta\neq 0$. If we can find such a $Y$ which is also normal to the affine plane (c.f. Fig. 1(b)), then the inner product above vanishes and (12) implies (10).

The main contribution of this work is an improved and generalized construction of an (approximate) dual certificate $Y$.

I-D Novel approaches

For readers well-accustomed to previous work, we shortly list some main technical differences.

We employ an i.i.d. sampling process (sampling with replacement) to chose the revealed coefficients. This contrasts with the “Bernoulli” scheme used before .

At two different points in the proof (Section II-C, Section II-F), we make use of a powerful large-deviation estimate for matrix-valued observables. This (so far under-appreciated?) operator Chernoff bound has been proven in .

In the language of , when constructing a “dual certificate”-type matrix $Y$ we note that it is sufficient to demand $\|\mathcal{P}_{T}E-Y\|_{2}$ be small, as opposed to zero (Section II-E). The former is simpler to ascertain than the latter.

We construct a particular matrix-valued random process (descriptively called the “golfing scheme”), which converges to the certificate $Y$ exponentially fast (Section II-F).

I-E Previous versions of this result and some related work

This work grew out of an effort to translate the results of to the problem of quantum-state tomography, where bases of Fourier-type matrices naturally occur. The project turned out to lead to more general results than anticipated, producing the methods presented in this paper.

We first published these results in , a short paper written with a physics audience in mind. This pre-print contains all the main ideas of the current work, and a complete proof of Theorem 3 for Fourier-type bases (the case of interest in quantum tomography). We announced in that a more detailed exposition of the new method, applying to the general low-rank matrix recovery problem with respect to arbitrary bases, was in preparation.

Before this extended version of had been completed, another pre-print building on appeared. The author of presents our methods in a language more suitable for an audience from mathematics or information theory. He also presents another special case of the results announced in : the reconstruction of low-rank matrices from randomly sampled matrix elements. The main proof techniques in are identical to those of , with two exceptions. First, the author independently found the same modification we are using here to extend the methods from Fourier-type matrices to bases with larger operator norm (his Lemma 3.6, our Lemma 10). Second, his proof works more directly with non-Hermitian matrices, and gives tighter bounds in the case of non-square matrices.

A more detailed version of focusing on physics issues will appear elsewhere .

II Main proof

Let $A_{1},\dots,A_{m}$ be random variables taking values in $[1,n^{2}]$. Their distribution will be specified momentarily. Important objects in our analysis are the matrix-valued random variables $w_{A_{i}}$. The sampling operator is

Below, we will analyze the semi-definite program

If the $A_{i}$’s correspond to $m$ samples drawn from $[1,n^{2}]$ without replacement, the programs (1) and (14) are equivalent. One can also consider the situation where the $A_{i}$’s are i.i.d. random variables, describing sampling with replacement. Due to independence, the latter situation is much easier to analyze. Independence also implies the possibility of collisions By the “birthday paradox”, such collisions are very likely to occur. (i.e. $A_{i}=A_{j}$, for $i\neq j$). In the presence of collisions, fewer than $m$ distinct coefficients will contribute to (14). It is thus plausible (and will be confirmed below) that any upper bound on the probability of failure of the i.i.d. scheme is also valid for (1). From now on, we will therefore assume that the $A_{i}$’s are independent and uniformly distributed.

To state the obvious: the solution $\sigma^{\star}$ to (14) is unique and equal to $\rho$ if and only if any non-zero deviation $\Delta=\sigma-\rho$ from $\rho$ is either infeasible

The two conditions (15), (16) have a very different mathematical flavor. Section II-C concentrates on the first one, while the second one is more central in the remainder.

Using (15), one can give a simple proof of our earlier remark that sampling with replacement can only decrease the probability of recovering $\rho$:

Let $\mathcal{R}^{\prime}$ be defined as in (13), but with the sum extending only over distinct samples $A_{i}\neq A_{j}$ (denote the number of distinct samples by $m^{\prime}$). Then $\ker\mathcal{R}^{\prime}=\ker\mathcal{R}$, and consequently (15) is true for $\mathcal{R}$ iff it is true for $\mathcal{R}^{\prime}$.

Thus, the probability that the solution to (14) equals $\rho$ is the same as the probability that the solution of

equals $\rho$. But, conditioned on any value of $m^{\prime}$, the distribution of $\mathcal{R}^{\prime}$ is the same as the distribution of a sampling operator drawing $m^{\prime}$ basis elements without replacement. Hence

The i.i.d. scheme used in the present papers contrasts with the “Bernoulli model” employed in previous works . There, every number $a\in[1,n^{2}]$ is included in $\Omega$ with probability $m/n^{2}$. The slight advantage of our approach is that the random variables $(w_{A_{i}},\rho)$ are identically distributed, in addition to being independent. Also, the random process analyzed here never obtains knowledge of more than $m$ coefficients, while this does happen in the Bernoulli model with finite probability. On the downside, the possibility of incurring collisions has some technical drawbacks, e.g. it means that $\mathcal{R}$ will in general not be proportional to a projection.

Note added: after the pre-print version of this paper had been submitted, V. Nesme and the author noted that existing arguments pertaining to sampling without replacing of real-valued random variables [22, Chapter 12] remain valid in the non-commutative case . In particular, all large deviation bounds derived below under the assumption of independently chosen coefficients continue to hold for $A_{i}$’s sampled without replacement. While we will not make use of these observations in the present paper, we note that they can be used to slightly improve the bounds given below. Details are in .

II-B Further layout of proof and notation

Following , decompose $\Delta=\Delta_{T}+\Delta_{T}^{\bot}$, with $\Delta_{T}\in T,\Delta_{T}^{\bot}\in T^{\bot}$ (see Fig. 2). (The reason for doing this will become clear momentarily).

In Section II-C we show that $\Delta$ is infeasible (fulfills (15)) as soon as $\|\Delta_{T}\|_{2}$ is “much larger” than $\|\Delta_{T}^{\bot}\|$.

The previous statement utilizes a large-deviation bound for operator-valued random variables, taken from . We repeat the proof of this powerful tool in Section II-D.

in Section II-E. Thus, as soon as the scalar product on the r.h.s. is positive, we conclude that $\Delta$ fulfills (16). We then borrow a powerful idea from , employing a “dual certificate”. More precisely it is shown that the aforementioned scalar product is guaranteed to be positive, as long as there is a matrix $Y\in\range\mathcal{R}$ such that (i) $\mathcal{P}_{T}Y$ is close to $\sign\rho$, and (ii) $\|\mathcal{P}_{T}^{\bot}Y\|$ is small.

Section II-F establishes the existence of a certificate $Y$ in the case of bases with small operator norm. This is probably the most (comparatively) difficult part of the proof, and the one differing most from previous approaches.

The construction of the previous section can be modified to work with any operator basis. Details are given in Section Section II-G. This completes the proof of the main result.

In Sections III-A, III-B we introduce some martingale techniques and put them to use to derive tighter bounds.

Section III-D deals with non-Hermitian matrices.

Throughout, we will use the notation $m=nr\kappa$. The “oversampling factor” $\kappa$ describes the leverage we allow ourselves by going beyond the minimum number of parameters needed to describe $\rho$.

Let $s_{i}$ be the singular values of a matrix $\sigma$. The usual matrix norms are

We will frequently encounter inequalities between matrices, which are understood in the usual sense: $\sigma_{1}\leq\sigma_{2}$ if and only if $\sigma_{1}-\sigma_{2}$ is positive semi-definite (a convention sometimes referred to as matrix order or Löwner partial order).

As mentioned in the introduction (Section I-A), $\sign\sigma$ is the matrix resulting from the application of the sign function to the eigenvalues of $\sigma$.

II-C First case: large ΔT\Delta_{T}

In this section, we show that $\Delta$ is infeasible (with high probability) if $\Delta_{T}$ is much larger than $\Delta_{T}^{\bot}$.

If $\|\mathcal{R}\Delta_{T}\|_{2}>\|\mathcal{R}\Delta_{T}^{\bot}\|_{2}$, then

To find criteria for this situation to occur, we need to put a lower bound on $\|\mathcal{R}\Delta_{T}\|_{2}$ and an upper bound on $\|\mathcal{R}\Delta_{T}^{\bot}\|_{2}$. For the latter:

It’s easy to see that $\|\mathcal{R}\|$ equals $n^{2}/m$ times the highest number of collisions $C:=\max_{i}|\{j\,|A_{i}=A_{j}\}|$. This number, in turn, is certainly smaller than $m$ (a truly risk-averse estimate). All in all:

This makes $\mathcal{P}_{T}\mathcal{R}\mathcal{P}_{T}$ an object of interest. Let $\mathcal{P}_{A_{i}}$ be the (matrix-valued) orthogonal projection onto $w_{A_{i}}$. Then the identity

We assume in the following that (21) holds with $t=1/2$. Denote the probability of that event not occurring by $p_{1}$. (Many statements in this proof will hold only up to a small probability of failure. We will defer an explicit calculation of these failure probabilities until the very end of the argument, when all parameters have been chosen). Then, using (19), (20), we have that $\mathcal{R}\Delta\neq 0$ if

For the next sections, it is thus sufficient to treat the case of

Remark: Repeating the calculations in this section without the trivial estimate $C<m$, the last coefficient in (22) can be improved from $n^{2}$ to $\sqrt{\frac{2C^{2}n}{\kappa r}}$. Since $C$ is $O(\ln n)$ with very high probability, this would look like a major improvement. However, because only the logarithm of the coefficient enters our final estimate of the number of samples required, we will content ourselves with $n^{2}$ on the grounds that it is a simpler expression.

II-D Operator large deviation bounds

The material in the first paragraph below is taken from . We repeat the argument to make the presentation self-contained. It is an elementary – yet very powerful – large deviation bound for matrix-valued random variables. The basic recipe is this: take a textbook proof of Bernstein’s inequality and substitute all inequalities between real numbers by matrix inequalities (in the sense of matrix order, see Sec. II-B).

We start by giving a basic Markov-inequality. Let $\Theta$ be the “operator step function” defined by

If $\sigma$ is positive semi-definite, the trivial estimate $\Theta(\sigma)\leq\tr\sigma$ holds. Thus, for any number $\lambda>0$ and matrix-valued random variable $S$:

Now let $X$ be an operator-valued random variable, $X_{i}$ be i.i.d. copies of $X$, and $S=\sum_{i}^{m}X_{i}$. Then

where the second line is the Golden-Thompson inequality .

These are all essential ingredients for the following theorem, summarizing the results from this section.

The second equation (28) will be used only once, in Section III-B.

Combine Eqs. (23, 25, 26) to get the estimate

Let $s=t/V$ be the deviation in units of $V$. Then

Choose $\lambda=s/(2V)$. The exponent becomes

valid as long as $\lambda\|X\|\leq 1$, which is certainly fulfilled if

If (29) does not hold, set $\lambda=1/c$ and compute for the exponent

The same estimates hold for $-S$, giving the advertised bound with the factor of $2$ coming from the union bound (which is also known as Boole’s inequality: the probability of at least one of a set of events occurring is not larger than the sum of their individual probabilities). ∎

Note that for $n=1$, we recover the standard Bernstein inequality, which we will also have the occasion to use.

We are in a position to supply the deferred proof of Lemma 5. Recall that it was claimed that

For $a\in[1,n^{2}]$, let $\mathcal{P}_{a}$ be the orthogonal projection onto $w_{a}$. We define a family of linear operators $Z_{a}$ by

From Eq. (4) we get $(w_{A_{i}},\mathcal{P}_{T}w_{A_{i}})\leq\frac{2\nu r}{n}$ and thus

having used that $Z_{A_{i}}\geq 0$ (matrix order). Hence

II-E Second case: small ΔT\Delta_{T}

together imply $\|\rho+\Delta\|_{1}>\|\rho\|_{1}$, if we can find a “certificate” $Y\in\range\mathcal{R}$ with certain properties. The basic line of argument is similar to the one given in Section 3 of .

Set $U=\range\rho$ and let $P_{U}$ be the orthogonal projection onto $U$. We will make repeated use of the basic identity

(recall the definition of $\sign$ from Section I-A). We then find

The estimate (32) is sometimes known as the “pinching inequality” (, Problem II.5.4), and in line (33) we used Hölder’s inequality: $(\sigma_{1},\sigma_{2})\leq\|\sigma_{1}\|\,\|\sigma_{2}\|_{1}.$

To conclude that $\|\rho+\Delta\|_{1}>\|\rho\|_{1}$, it is hence sufficient to show that $(\sign\rho+\sign\Delta_{T}^{\bot},\Delta)>0.$ Choose any $Y\in\range\mathcal{R}$. Using (31):

We summarize. Assume there is a certificate $Y\in\range\mathcal{R}$ fulfilling (36). Let $\sigma^{\star}$ be the solution of the optimization problem, let $\Delta^{\star}=\rho-\sigma^{\star}$. Then $\Delta^{\star}$ must fulfill (31), for else it would be unfeasible. It must also fulfill (30), by Section II-C. But then, from the previous calculation $(\Delta^{\star})_{T}^{\bot}$ must be zero, as otherwise $\|\sigma^{\star}\|_{1}>\|\rho\|_{1}$. This implies that $(\Delta^{\star})_{T}$ is also zero, again using (30). So $\Delta^{\star}$ is zero, and therefore $\sigma^{\star}=\rho$ is the unique solution to (14).

It remains to prove the existence of the certificate $Y$.

II-F The certificate: bases of Fourier type

In this section, we construct a $Y\in\range\mathcal{R}$ with

assuming that $\max_{a}\|w_{a}\|^{2}\leq\frac{\nu}{n}$. A modified proof valid in the general case will be given in Section II-G. In previous approaches to matrix completion, this step was the most involved, covering dozens of pages. We present a strongly simplified proof using two key ideas: a further application of the operator Bernstein inequality; and a certain, recursive random process which quickly converges to the sought-for $Y$.

A first, natural ansatz for finding $Y$ could be as follows. Define

It is obvious that $Y$ is in the range of $\mathcal{R}$ and that its expectation value (equal to $\sign\rho$) fulfills the conditions in (37). What is more, the operator Chernoff bound can be used to control the deviation of $Y$ from that expected value – so there is hope that we have found a solution. However, a short calculation shows that convergence is (barely) too slow for our purposes.

Intuitively, it is easy to see what is “wrong” with the previous random process. Assume we sample $k<m$ basis elements. Employing (38), our general “best guess” at this point for a matrix $Y_{1}$ which resembles $\sign\rho$ on $T$ (i.e. with $\|\mathcal{P}_{T}Y_{1}-\sign\rho\|_{2}$ “small”) would be

Now given this information, the matrix we really should be approximating in the next steps is $\mathcal{P}_{T}(\sign\rho-Y_{1})$. The process (38), in contrast, does not update its “future strategy based on past results”. Trying to perform better, we will draw a further batch of $k$ coefficients and set

The sequence $\mathcal{P}_{T}Y_{i}$ will be shown to converge exponentially fast to $\sign\rho$. For reasons which should be all too obvious from Fig. 3, we will call this adapted strategy the golfing scheme.

On the one hand, the size $k$ of the batches will have to be chosen large enough to allow for the application of the operator large-deviation bounds tailored for independent random variables. On the other hand, $k$ must not be too large, as the speed of convergence is exponential in $l=m/k$.

II-F2 Proof

Before supplying the details of this scheme, we state a lemma which will allow us to control the operator norm $\|\mathcal{P}_{T}^{\bot}Y\|$ of the approximations. The operator-Bernstein inequality makes this, once again, a simple calculation.

It suffices to treat the case where $\|F\|_{2}=1$. Set

Then $\sum_{i}^{m}X_{A_{i}}=\mathcal{P}_{T}^{\bot}\mathcal{R}F$, and

Using (3) and the fact that $\|\mathcal{P}_{T}^{\bot}w_{a}\|\leq\|w_{a}\|$ we estimate the variance:

We sample $l$ batches of basis elements, the $i$th set consisting of $m_{i}=\kappa_{i}rn$ matrices.

be the sampling operator associated with the $i$th batch and set

Denote the probability of this event not occurring by $p_{2}(i)$ (recall that $p_{1}$ has been defined in Section II-C). Clearly, if (41) does hold for all $i$, then

so that $\|X_{i}\|_{2}\leq\sqrt{r}\prod_{j=1}^{i}c_{j}$.

Assume further that for all $i$ the estimate

is true, with $p_{3}(i)$ bounding the probability of failure.

A first simple choice of parameters (to be refined in Section III-B) is

With $l=\lceil\log_{2}(2n^{2}\sqrt{r})\rceil$, the conditions in Equation (37) are met. Using Lemma 5 and Lemma 7 the failure probabilities become

all of which are bounded above by $\frac{1}{2l}n^{-\beta}$. Theorem 3 for Fourier-type bases thus follows from a simple application of the union bound. The number of coefficients sampled must exceed

II-F3 Discussion

The “golfing scheme” above could be described as a “sequential” way of building the certificate vector: every time we sample a basis element $w_{a}$, we assign a coefficient $c_{a}=(w_{a},X_{i})$ to it, but never alter our previous choices. This contrasts with the more “holistic” method employed in , where $Y$ was constructed by directly inverting $\mathcal{P}_{T}\mathcal{R}\mathcal{P}_{T}$:

Presumably, the most optimal sequential scheme is the one which chooses the coefficient $c_{a}$ in every step such as to minimize the distance to the vector we aim to approach. If the distance is measured in 2-norm, it is simple to write down a closed-form expression for that choice. However, such a strategy introduces strong dependencies into the random process, which make an analysis challenging. The elementary i.i.d. tools employed in this paper are no longer applicable. This intuition motivates considering martingale generalizations of the operator-large deviation bounds of . We will indeed prove a deviation estimate for matrix-valued martingales in Section III-A. Whether this bound is sufficient to analyze the “optimal sequential scheme” remains unclear.

We remark that analyzed (42) by expanding the inverse into a Neumann series

II-G The certificate: general case

In this section, we show that the construction of $Y$ described above continues to work if the assumption (3) on the operator norm of the basis elements is replaced by the incoherence properties (4, 5).

Indeed, in the discussion of the golfing scheme, we referred to the operator norm of $w_{a}$ exactly once. In the proof of Lemma 7, we considered the quantity

was upper-bounded using the fact that $\|(\mathcal{P}_{T}^{\bot}w_{a})^{2}\|\leq\frac{\nu}{n}$. Clearly the absence of this assumption can be compensated for by a suitable bound on $(w_{a},F)^{2}$. This will be made precise below.

Assume that $F$ is some matrix in $T$ with $\|F\|_{2}=1$. Further, assume that at least one of the following two bounds

respectively. The assumption that $\|F\|_{2}^{2}=1$ implies that $\|q\|_{1}=\sum_{a}|q_{a}|=1$. Slightly less obvious is the fact that the same is true for the other vector: $\|p\|_{1}=1$, regardless of the basis chosen. This relation is ascertained by the next lemma.

Let $\{w_{a}\}$, be a set of $n\times n$-matrices (not necessarily Hermitian) that fulfill the completeness relation

We return to the vectors in (48). The assumptions made imply that at least one of the vectors is element-wise bounded above by $\frac{\nu}{n^{2}}$. Thus

Plugging this estimate into the computation of the variance (47) we obtain

We have proved the general analogue of Lemma 7:

Let $F\in T$. Let $f\geq\|F\|_{2}$ be an upper bound on the 2-norm of $F$. Assume that one of the two bounds

Let $\mu(F)=\max_{a}(w_{a},F)^{2}$ be the maximal squared overlap between $F$ and any element of the operator basis.

The advertised estimate follows by taking squares and applying the union bound over the $n^{2}$ elements of the basis. ∎

With these preparations made, we can repeat the “golfing” argument from the last section. As an additional constraint, we demand that

be fulfilled for all $i$, with probability of failure given by $p_{4}(i)$.

Thus, in $i$th iteration of the golfing scheme, we can apply Lemma 9 with $F=X_{i}$ and $f=2^{-i}\sqrt{r}$.

The failure probabilities $p_{1},p_{2}(i)$ and $p_{3}(i)$ are as before. Further

which, as the other probabilities, is bounded above by $\frac{1}{3l}n^{-\beta}$. By the union bound, Theorem 3 holds as long as

III Refined methods and generalizations

The purpose of this section is two-fold. First, we derive a dimension-free bound for the norm of the sum of vector-valued random variables (Theorem 12). Substituting Lemma 5 by this dimension-free analogue will enable us to give tighter bounds of matrix recovery in Section III-B (see discussion in Section II-F3). Such dimension-free bounds for sums of vectors are well-known and we could in principle content ourselves with citing an existing version. Making the proof explicit, however, ensures that this document remains self-contained and allows us to record a corollary which may be of independent interest. Indeed, the simplest argument in relies on a standard large-deviation bound for real-valued martingales. We use the occasion to prove an operator version (Theorem 11) of this martingale estimate, which generalizes the operator Chernoff bound. This constitutes the second purpose of the present section.

Let $X_{1},\dots,X_{m}$ be a sequence of random variables. We will use the bold-face symbol $\mathbf{X}_{i}$ to refer to the set $\{X_{1},\dots,X_{i}\}$ of the first $i$ of these variables. Theorem 11 is an almost verbatim translation of the real-valued statement in (see also ). To lift it to operator-valued variables, we use exactly the same tricks that were employed in to obtain the operator Chernoff bound (c.f. our exposition in Section II-D).

Let $X_{0},\dots,X_{m}$ be arbitrary random variables. Let $Z_{0}=0$ and let $Z_{1},\dots,Z_{m}$ be a sequence of ($n\times n$)-Hermitian matrix-valued random variables. Assume the martingale condition

holds for $i=1,\dots,m$. Assume further that the martingale difference sequence $D_{i}=Z_{i}-Z_{i-1}$ respects

Then, with $V=\sum_{i}^{m}\sigma_{i}^{2}$,

for any $\lambda>0$. Using Golden-Thompson:

Once more, we will make use of the estimate $1+y\leq e^{y}\leq 1+y+y^{2}$ valid for $|y|\leq 1$:

as long as $\lambda\|D_{i}\|\leq 1$. Thus

The claim follows by setting $\lambda=t/2V$. ∎

The next theorem is essentially contained in Chapter 6 of (see also ). To keep the presentation self-contained, we give a short proof in Appendix VI.

Let $X_{1},\dots,X_{m}$ be independent zero-mean vector-valued random variables. Let

We can now prove a non-uniform, but dimension independent version of Lemma 5.

Note added: After the pre-print version of this paper was published, the author was made aware of a related matrix-valued martingale bound in . The derivations used in are very similar in spirit to ours (however, their results cannot be applied directly to the problem treated here, because no variance information is incorporated). A few months after our pre-print appeared, more sophisticated matrix-valued martingale bounds were established in .

III-B Tighter bounds for Fourier-type bases

We present a refined analysis of the “golfing scheme”, which achieves fairly tight bounds for Fourier-type bases. Compared to Section II-F, there are two changes in the argument. First, we use the dimension-free large deviation bound for vectors derived in the previous section. Second, the parameters of the random process used to construct the certificate are chosen more carefully.

Let $\alpha>4$ be a number to be chosen later. We will analyze the following set of parameters for the golfing scheme:

We look at the failure probabilities. To bound $p_{2}(i)$, we make use of the dimension-free estimate provided by Lemma 13:

The failure probabilities concerning the assertions about $\|\mathcal{P}_{T}^{\bot}Y\|$ are bounded, as before, by Lemma 7. Note that we need to employ the “Poissonian” part of the lemma, i.e. Eq. (28) when $i>2$.

Lastly, $p_{1}$ can be comfortably bounded by

A first improved estimate may be achieved at this point by setting $\alpha=2l$. From a simple application of the union bound we infer that the total probability of error is smaller than $e^{-\beta}$. In total, the process will have accessed fewer than

Let $\rho$ be a rank-$r$ matrix and suppose that $\{w_{a}\}$ is an operator basis fulfilling $\max_{a}\|w_{a}\|^{2}\leq\frac{\nu}{n}$. Then the solution $\sigma^{\star}$ to the optimization problem (1) is unique and equal to $\rho$ with probability of failure smaller than $e^{-\beta}$, provided that

Largely for aesthetic reasons, we provide a further refinement which does away with the $(\ln\ln n)$-term in (56). Recall its origin. Let $p(i)\leq p_{1}(i)+p_{2}(i)$ be the probability that at least one of the two assumptions

made about the $i$th batch does not hold. In the argument above, we employed the union bound which ascertains that the total probability of failure is bounded above by $l\max_{i}p(i)$. To make this expression a constant, $\max_{i}p(i)$ must be $O(l^{-1})$. This, in turn, was achieved by setting $\alpha=O(\ln l)=O(\ln\ln n)$.

There is an alternative construction for the dual certificate which turns out to yield a better estimate. Informally, the idea is to draw $l^{\prime}>l$ batches, but to include into the golfing scheme only those batches for which the assumptions (57), (58) hold. We must choose $l^{\prime}$ large enough that, with high probability, $l$ of the batches do fulfill the assumptions. There is hence a further degree of freedom in the choice of the parameters: decreasing the $\kappa_{i}$ increases the average number of batches not meeting the assumptions, which can be compensated for by increasing $l^{\prime}$. It will be shown below that this freedom may be used to improve the bounds.

To give a formal description of the construction, we re-state the slightly modified definitions of the objects occurring in the golfing scheme. The most important change is the introduction of a function $f:[1,l]\to[1,l^{\prime}]$ which enumerates the batches to be included. More precisely, the objects

now only depends on a subset of batches. The function $f$, in turn, is defined by setting $f(0)=0$ and $f(i)$ to

It remains to choose the parameters of the golfing scheme. With foresight, set $\alpha=6$. Then the probability $p(i)$ of the $i$th batch ($i>2$) being discarded (i.e. $i$ not being in the range of $f$) is smaller than

By the standard Chernoff-Hoefding bound E.g. Theorem 2.3a in ; one could also use the Bernstein inequality derived in this paper, obtaining slightly worse constants.:

We consider this bound in two regimes. First assume that $n\geq 2^{5(\beta+\ln 6)}$ so that $l\geq 2\log_{2}n\geq 9(\beta+\ln 6)$. Choose $l^{\prime}=2l$. The exponent becomes $-\frac{l}{9}\leq-(\beta+\ln 6)$. Next, drop the assumption on $n$ and instead demand $\beta\geq 8+3\ln 6$. Set $l^{\prime}=\beta\frac{3}{2}l$. In this case a few simple manipulations yield for the exponent

By the union bound, the total probability of failure is smaller than

Under the first assumption ($n\geq 2^{5(\beta+\ln 6)}$) the scheme required knowledge of fewer then

coefficients. In the second case ($\beta\geq 8+3\ln 6$) the number is

Remark: All the arguments of this section remain valid when the bound on the operator norm of the basis is dropped. The sole obstruction preventing us from stating $O(rn\nu\ln n)$ bounds for the more general case is the union bound in Lemma 10. While it seems plausible that one can overcome this difficulty with reasonable effort, the author has so far failed to do so.

III-C A lower bound

Reference gave lower bounds of order $O(nr\nu\ln n)$ for the number $|\Omega|$ of matrix elements necessary to fix a rank-$r$ matrix. Since the theory of low-rank matrix recovery seems better-behaved for Fourier-type bases, it might be conjectured that fewer coefficients are sufficient in this case. This hope turns out not to be realized.

The results of this section imply that the bound of Theorem 4 is tight up to multiplicative constants.

Let $n=2^{k}$ be a power of two. Let $\{w_{a}^{(k)}\}$ be the Pauli basis defined in Section I-B2.

Let $\Omega$ be any subset of $[1,n^{2}]$. If $|\Omega|<(n-2)\log_{2}n$, then there are two rank-one projections $P_{1},P_{2}$ with orthogonal range such that $(w_{a},P_{1})=(w_{a},P_{2})$ for all $a\in\Omega$.

There is a rank-one projection $P_{1}$ with the following property. Let $\Omega$ be a set of numbers in $[1,n^{2}]$, obtained by sampling

times with replacement. Then with probability

there exists a rank-one projection $P_{2}$, orthogonal to $P_{1}$, such that $(w_{a},P_{1})=(w_{a},P_{2})$ for all $a\in\Omega$.

The proof makes use of the theory of stabilizer states, a common notion in quantum information theory . To make the presentation self-contained, we have included the briefest outline of this theory as Appendix VII. The proof below assumes familiarity with the notions introduced in the appendix.

In the statement of the theorem, we used a “one-dimensional” labeling of the Pauli basis elements $w_{a}$ by numbers $a\in[1,n^{2}]$. In Section VII on stabilizer theory, a “two-dimensional” labeling in terms of pairs $(p,q)$ from $[1,n]\times[1,n]$ proved more convenient. We assume that some mapping identifying the one set with the other has been chosen and will subsequently not distinguish between them.

We turn to the second claim. Take $P_{1}=P(G_{x},\chi)$ for some stabilizer group $G_{x}$ as in Prop. 23 and some character $\chi$. As $|G|=n$, the probability of a randomly chosen element of the basis to be contained in $G$ equals $1/n$. As argued before, there will be an orthogonal stabilizer projector $P_{2}$ compatible with the coefficients in $\Omega$, as soon as the intersection between $\Omega$ and $\{w_{a}\,|\,a\in\Omega\}$ is smaller than $k=\log_{2}n$. Thus the probability that (1) has a unique solution is not larger than the probability of an event with probability $1/n$ occurring at least $\log_{2}n$ times in $m=n\log_{2}n/(1-\epsilon)$ trials. This quantity can be bounded by the standard Chernoff-Hoefding inequality (e.g. , Theorem 2.3. (b)). The advertised bound follows. ∎

III-D Non-Hermitian setting

We presented the argument in terms of Hermitian matrices because this is the natural setting for the Operator-Bernstein inequality. It is, however, straight-forward to extend the results to arbitrary complex matrices. The construction in this section serves as a simple proof of principle; a more refined analysis is certainly possible.

Indeed, assume both $\rho$ and the $\{w_{a}\}$ are arbitrary complex $n\times n$ matrices (in this section, we break with our previous convention that any matrix is automatically assumed to be Hermitian unless stated otherwise). We will employ a standard construction , associating with any complex $n\times n$-matrix $\sigma$ a Hermitian $2n\times 2n$-matrix

The obvious strategy pursued below consists of the following steps:

from $\{w_{a}\}$, build a suitable Hermitian basis in the space $\mathcal{M}_{2n}$ of $2n\times 2n$ matrices,

apply the methods detailed in this paper in the extended space, and

show that the original matrix recovery algorithm (i.e. the program (1) applied to $\rho$, $\{w_{a}\}$ is no more likely to fail than the one in the extended space.

For $\sigma_{1},\sigma_{2}\in\mathcal{M}_{n}$:

Let $\{w_{a}\}_{a}$ be an ortho-normal basis in the complex vector space $\mathcal{M}_{n}$. Then

is an ortho-normal basis in the real vector space of Hermitian off-diagonal matrices of the form (59).

(the non-Hermitian analogue of $\sign\sigma$; c.f. ). Then

which implies the first two claims. Verifying statement 3 is trivial.

where the minimization is over all Hermitian matrices $\sigma$ in $\mathcal{M}_{2n}$. This is step (ii) above. (Note again that we are interested in the program (65) only as a means of proving that the original program (1) works directly for non-Hermitian objects).

To handle step (iii), we introduce further notations. Let $U=\range\rho,V=\range\rho^{\dagger}$ be the row and column space of $\rho$ respectively. Generalizing our earlier definition to non-Hermitian operators (and following ), let $T$ be the space of matrices with row space contained in $U$ or column space contained in $V$. The projection operator $\mathcal{P}_{T}$ onto $T$ acts as

From the analogous relation for the adjoint we conclude that

so that the claim follows from Lemma 16.1. ∎

The $n\times n$-matrix $\rho$ has coherence $\nu$ with respect to a basis $\{w_{a}\}$ if either

The bounds of Theorem 3 and Theorem 4 continue to hold for non-Hermitian $\rho$ and $\{w_{a}\}$, if the coherence $\nu$ is measured according to Definition 18, and $n$, $r$ are substituted by $2n$, $2r$ respectively.

IV Conclusion and Outlook

The following topics will be treated in follow-up publications.

As indicated in , the procedures laid out in this paper are resilient against noise. The analysis of noise effects in the general case builds on techniques proved in for the matrix completion problem. It turns out that the bounds are quite sensitive to the operator norm of the sampling operator $\mathcal{R}$ (c.f. Eq. (18)). This number is equal to one if the expansion coefficients were sampled without replacing, and is likely to be of order $O(\ln n)\gg 1$ for the i.i.d. scheme presented here. In a future publication, we will prove operator-valued large deviation bounds for sampling without replacing . Therefore, a detailed discussion of noise effects will be deferred until then.

IV-A2 Tight frames

Let $\mu$ be a normalized measure on the unit-sphere of matrices. We refer to $\mu$ as a tight frame (also a spherical 1-design or a set of matrices in isotropic position , or just an “overcomplete basis”) if

where $\mathcal{P}_{w}$ is the orthogonal projection onto $w$. Tight frames can replace ortho-normal bases in many situations.

In the “Fourier-type” case – i.e. if there is a uniform bound on the operator norm $\|w\|$ of the elements of the frame – all statements in this paper may be easily translated from ortho-normal bases to tight frames. In the absence of such a constraint, Lemma 10 may be a source of problems: it contains a union bound over all elements of the frame and is therefore sensitive to its size. In particular, it cannot be directly applied to continuous frames. We believe that this difficulty can be overcome with medium effort and may present more details elsewhere.

Note that similar conclusions have been drawn before in the case of commutative compressed sensing .

V Acknowledgments

The author is glad to acknowledge inspiring discussions with, and the support of, I. Bjelakovic, S. Becker, S. Flammia, M. Kleinmann, V. Nesme. In particular, he would like to thank J. Eisert and Y.-K. Liu for providing many insights which lead to improvements of the argument. The manuscript benefited considerably from constructive comments by the anonymous referees.

VI Appendix A: proof of Theorem 12

For completeness, we give a short proof of Theorem 12 (see also ).

We aim to use Theorem 11 with $n=1$. To that end, let

Let $\hat{\mathbf{X}}_{i}$ be the set $\{X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{m}\}$ of all random variables except for the $i$th one. Finally, let

be the sum of all vectors, with the $i$th term omitted.

where the maximum is over all values of $X_{i}$. With (73):

VII Appendix B: basic theory of stabilizer states

The lower bound in Section III-C was built around the concept of “stabilizer states”, a concept from quantum information theory. For the convenience of the reader, we give a short outline below. The presentation is necessarily both very condensed and fairly technical. A more complete account can be found e.g. in Refs. .

As a first step, we need to identify a certain group structure of the elements of the Pauli basis introduced in Section I-B2.

With $w(p,q)$ as defined in (75), it holds that

The $w(p,q)$’s are Hermitian and unitary. It follows that

The Pauli operators form an super-normalized orthogonal basis:

If $w(p,q)$ and $w(p^{\prime},q^{\prime})$ commute, then (78) simplifies to

Equations (76, 77, 78, 80) can be checked by simple direct computation.

To verify Eq. (79), note that the product of two commuting Hermitian operators is Hermitian. Thus, if $w(p,q)$ and $w(p^{\prime},q^{\prime})$ commute, the l.h.s. of (78) is Hermitian. But the r.h.s. is Hermitian only if $\lambda(p,q,p^{\prime},q^{\prime})$ is real. ∎

forms a matrix group which is known as the Pauli group.

Certain subgroups of the Pauli group can be used to define an interesting class of projection operators. These are called stabilizer groups and defined as follows:

Let $G$ be a subgroup of $\mathcal{P}^{(k)}$. The group $G$ is called a stabilizer group if

The connection between stabilizer groups and projection operators is given in the next proposition.

Let $G$ be a stabilizer group. Let $\chi$ be a complex character of $G$ (i.e. $\chi(gg^{\prime})=\chi(g)\chi(g^{\prime})$ for $g\in G$). Set

In particular, $P(G,\chi)$ is a rank-one projector.

If $\chi^{\prime}$ is another complex character of $G$, then

because for $h\in G$ it holds that $h\,G=G$ (which is true for any group).

having used Eq. (77) and the standard orthogonality relation for characters of finite groups (see e.g. [37, Corollary 2.14]. ∎

the generators commute mutually by Eq. (80). Thus, $G_{x}$ is Abelian.

References