Von Neumann Entropy Penalization and Low Rank Matrix Estimation

Introduction

$\xi_{j},\ j=1,\dots,n$ being i.i.d. random variables with mean zero and finite variance representing measurement errors. In other words, the unknown state $\rho$ of the system is to be learned based on a set of measurements in a number of “directions” $X_{j},j=1,\dots,n$ (see Artiles, Gill and Guta (2004) for a general discussion of statistical problems in quantum state tomography). In what follows, it will be usually assumed that the design variables $X,X_{1},\dots,X_{n}$ are also random, specifically, they are i.i.d. Hermitian $m\times m$ matrices with distribution $\Pi,$ and they are independent of the noise $\{\xi_{j}\}.$

The following simple example is related to the problems of matrix completion extensively discussed in the recent literature (see, e.g., Candes and Recht (2009), Candes and Tao (2009), Recht (2009) and references therein). More precisely, it deals with a version of matrix completion for Hermitian matrices (see Gross (2009)). In this case, when one knows an entry $\rho_{ij}$ of a matrix $\rho,$ one also knows the entry $\rho_{ji}=\bar{\rho}_{ij}.$

which will be called the matrix completion basis. Here and in what follows $\otimes$ denotes the tensor product of vectors or matrices. Note that, for a Hermitian matrix $\rho,$ observing inner products $\langle\rho,E_{i}\rangle$ with randomly picked matrices $E_{i}$ from the above basis provides information about real and imaginary parts of the entries of the matrix, which explains the connection to the matrix completion problems. Another option is to consider the following basis of the space of all Hermitian matrices:

Another example was studied by Gross et al (2009) and by Gross (2009). It is more directly related to the problems of quantum state tomography.

The problems of this nature belong to a rapidly growing area of low rank matrix recovery. The most popular methods developed so far are based on nuclear norm regularization.

and we will often use the corresponding $L_{2}(\Pi)$-distance between matrices (say, between two states $S_{1},S_{2}\in{\cal S}$). This distance represents the prediction error in statistical problems in question.

In the noiseless case (i.e., when $\xi_{j}\equiv 0$), the following estimator of $\rho$ has been extensively studied, especially, in the case of matrix completion problems (see Candes and Recht (2009), Candes and Tao (2009), Gross (2009), Recht (2009) and references therein):

Under some assumptions that resemble the restricted isometry conditions used in compressed sensing, it was shown that, with a high probability, $\hat{\rho}=\rho$ provided that the number $n$ of observations is sufficiently large. Namely, up to logarithmic factors and constants, it should be of the order $mr,$ where $r$ is the rank of the target matrix $\rho.$

In the noisy case, one has to deal with a matrix regression problem and the following penalized least squares estimator, which is akin to the LASSO used in sparse regression, was proposed and studied (see, e.g., Candes and Plan (2009), Rohde and Tsybakov (2009)):

where $\varepsilon$ is a regularization parameter. Note that these estimators are not constrained to the set ${\cal S}$ of density matrices (since for these matrices the nuclear norm is equal to $1$). Candes and Plan (2009) have also studied another estimator based on the nuclear norm minimization subject to linear constraints that resembles the Dantzig selector used in compressed sensing and Rohde and Tsybakov (2009) suggested estimators based on nonconvex penalties involving Schatten “$p$-norms” for $p<1.$

We will study the following estimator of the unknown state $\rho$ defined as a solution of a penalized empirical risk minimization problem:

where $\varepsilon>0$ is a regularization parameter. The penalty term is based on the functional ${\rm tr}(S\log S)=-{\cal E}(S),$ where ${\cal E}(S)$ is the von Neumann entropy of state $S.$ Thus, the method considered in this paper is based on a trade-off between fitting the model by the least squares in the class of all density matrices and maximizing the entropy of the state.

One can also consider a slightly different estimator defined as follows:

Of course, the estimator (1.3) requires the knowledge of the design distribution $\Pi$ while the estimator (1.2) can be also used in the cases when $\Pi$ is unknown. It happens that it is somewhat easier to study the properties of estimator (1.3) than of (1.2) for which one has to deal with more complicated empirical processes. Note that both optimization problems (1.2) and (1.3) are convex (this is based on convexity of the penalty term that follows from the concavity of von Neumann entropy, see Nielsen and Chuang (2000)). In what follows, we will study only the estimators defined by (1.2).

A commutative version of entropy penalization and its connections to sparse recovery problems in convex hulls of finite dictionaries have been studied by Koltchinskii (2009). In the current paper, this approach is extended to the noncommutative case.

An Overview of Main Results

The results of this paper include oracle inequalities for the $L_{2}(\Pi)$-error of the empirical solution $\hat{\rho}^{\varepsilon}.$ They will be stated in a general form in sections 5 and 6. Here we formulate our results only in two of the special examples outlined in the Introduction: subgaussian isotropic design (such as Gaussian or Rademacher) and random sampling from the Pauli basis. Assume, for simplicity, that the noise $\{\xi_{j}\}$ is a sequence of i.i.d. $N(0,\sigma_{\xi}^{2})$ random variables (i.e., it is a Gaussian noise).

Let $t>0$ be fixed and denote $t_{m}:=t+\log(2m),\ \ \tau_{n}:=t+\log\log_{2}(2n).$

Suppose $X$ is a subgaussian isotropic matrix. There exist constants $C>0,c>0$ such that the following holds. Under the assumption that $\tau_{n}\leq cn,$ for all $\varepsilon\in,$ with probability at least $1-e^{-t}$

Moreover, there exists a constant $D>0$ such that, for all \varepsilon\geq D\sigma_{\xi}\biggl{(}\sqrt{\frac{mt_{m}}{n}}\vee\frac{\sqrt{m}t_{m}}{n}\biggr{)}, with probability at least $1-e^{-t},$

This theorem includes two bounds on the $L_{2}(\Pi)$-error of $\hat{\rho}^{\varepsilon}.$ The first bound (1) holds for all $\varepsilon$ including $\varepsilon=0,$ which is the case of the unpenalized least squares estimator. The term \varepsilon\biggl{(}\|\log\rho\|\wedge\log\frac{m}{\varepsilon}\biggr{)} in this bound depends on the operator norm of $\log\rho$ and it has to do with the approximation error of the entropy penalization method (see Section 4). The second bound (1) is an oracle inequality that controls the squared $L_{2}(\Pi)$-error of the estimator $\hat{\rho}^{\varepsilon}$ in terms of approximation errors of oracles $S\in{\cal S}.$ The term $\varepsilon^{2}\|\log S\|_{2}^{2}$ in this bound is also related to the approximation error of the entropy penalization method discussed in Section 4. This term depends on the Hilbert-Schmidt norm of $\log S.$ The dependence on $\varepsilon$ is better than in the first bound, but bound (1) holds only for the values of regularization parameter above certain threshold. Clearly, in the second bound, the oracles $S$ are to be of full rank (otherwise, $\log S$ does not exist and the right hand side of the bound becomes infinite). The random errors in these bounds are also different. In the first bound, it is of the order $n^{-1/2}$ (up to logarithmic factors). In the second bound, the error term depends on how well the oracle $S$ is approximated by low rank matrices. If there exists a subspace $L$ of small dimension ${\rm dim}(L)$ such that $\|P_{L^{\perp}}SP_{L^{\perp}}\|_{1}$ is small (say, of the order $n^{-1/2}$), then the random part of the error in (1) is essentially controlled by $\sigma_{\xi}^{2}\frac{{\rm dim}(L)m}{n}.$

It will be shown later in the paper how to derive from the bounds of Theorem 1 and more general bounds for oracles of full rank some other inequalities for low rank oracles. In particular, for subgaussian isotropic design and Gaussian noise, this approach yields the following result. To simplify its formulation, we will assume that, for some constant $c>0,$ $\tau_{n}\leq cn$ and $t_{m}\leq n.$

Suppose $X$ is a subgaussian isotropic matrix. There exist a constant $c>0$ and, for all sufficiently large $D>0,$ a constant $C>0$ such that, for $\varepsilon:=D\sigma_{\xi}\sqrt{\frac{mt_{m}}{n}},$ with probability at least $1-e^{-t},$

A simple consequence of the first bound of Theorem 1 and the bound of Theorem 2 is the following inequality that holds with probability at least $1-e^{-t}$ and with some $C>0$ for $\varepsilon:=D\sigma_{\xi}\sqrt{\frac{mt_{m}}{n}}:$

Suppose that $X$ is sampled at random from the uniform distribution $\Pi$ on the Pauli basis. Then, there exists a constant $C>0$ such that, for all $\varepsilon\in,$ with probability at least $1-e^{-t},$

In addition, for all sufficiently large $D>0,$ there exists a constant $C>0$ such that, for

Similarly to the previous theorems, one can easily derive from Theorem 3 the following bound

that holds with probability at least $1-e^{-t}$ and with some $C>0$ for $\varepsilon=D(\sigma_{\xi}m^{-1/2}\vee m^{-1})\sqrt{\frac{t_{m}}{n}}.$

It is worth mentioning that the results of sections 4, 5 provide a way to bound the error of estimator $\hat{\rho}^{\varepsilon}$ not only in the $L_{2}(\Pi)$-distance, but also in other statistically important distances such as noncommutative Kullback-Leibler, Hellinger and nuclear norm distance (see Section 3.1 for their definitions). For instance, under the assumptions of Theorem 1, the following bound for the symmetrized Kullback-Leibler distance holds with probability at least $1-e^{-t}:$

In the case of sampling from Pauli basis (as in Theorem 3), it is easy to derive from Theorem 5 of Section 5 (using also some bounds from the proofs of Proposition 5 and Corollary 1) the following bound on the squared Hellinger distance between $\hat{\rho}^{\varepsilon}$ and $\rho:$

that holds with probability at least $1-e^{-t}$ for $\varepsilon=D(\sigma_{\xi}m^{-1/2}\vee m^{-1})\sqrt{\frac{t_{m}}{n}}.$

It has been already mentioned that the first bounds of theorems 1 and 3 (bounds (1) and (2.4)) hold for all $\varepsilon\geq 0,$ even in the case of unpenalized least squares estimator with $\varepsilon=0.$ The random error parts of these bounds are (up to logarithmic factors) of the order $n^{-1/2}$ as $n\to\infty.$ Bounds (1), (2.3) and (2.5) are based on more subtle analysis taking into account the ranks of the oracles $S$ approximating the true density matrix $\rho.$ In these bounds, the size of the $L_{2}(\Pi)$-error $\|\hat{\rho}^{\varepsilon}-\rho\|_{L_{2}(\Pi)}^{2}$ is determined by a trade-off between the approximation error $\|S-\rho\|_{L_{2}(\Pi)}^{2}$ of an oracle $S$ and the random error. In the case of bounds (2.3) and (2.5), the last error is of the order $\frac{\sigma_{\xi}^{2}{\rm rank}(S)m}{n}$ (up to logarithmic factors), and it depends on the rank of the oracle $S.$ In particular, taking $S=\rho,$ we can conclude that $\|\hat{\rho}^{\varepsilon}-\rho\|_{L_{2}(\Pi)}^{2}$ is bounded by $\frac{\sigma_{\xi}^{2}{\rm rank}(\rho)m}{n}$ (up to constants and logarithmic factors). This means that von Neumann entropy penalization mimics oracles that know precisely which low rank matrices approximate $\rho$ well and can estimate $\rho$ by estimating a “small” number of parameters needed to describe such oracles. This could be compared with recent results for nuclear norm penalization (Candes and Plan (2009), Rohde and Tsybakov (2009)). Depending on the values of $\sigma_{\xi},m,n$ and other characteristics of the problem more “rough” bounds (1) and (2.4) might become even sharper than more “subtle” bounds (1), (2.3) and (2.5) (see Rohde and Tsybakov (2009) for a discussion of a similar phenomenon). Since the random error term in more “subtle” bounds is proportional to $\sigma_{\xi}^{2}$ and in the “rough” bounds it is proportional to $\sigma_{\xi},$ the “rough” bounds become sharper for the values of standard deviation of the noise $\sigma_{\xi}$ above a threshold that depends on $n$ and $m.$ Thus, the rate of convergence of the $L_{2}(\Pi)$-error to zero in a particular asymptotic scenario (when certain characteristics are large) is determined by the bounds of both types.

Theorems 1, 2, 3 and other results of a similar nature will follow as corollaries from more general oracle inequalities that we establish under broader assumptions on the design distributions and on the noise. To prove these results, we need several tools from the empirical processes and random matrices theory, such as noncommutative Bernstein type inequalities and generic chaining bounds for empirical processes. We will discuss these results in Section 3 (as well as some properties of noncommutative Kullback-Leibler, Hellinger and other distances between density matrices). We will then study approximation error bounds for the solution of von Neumann entropy penalized true risk minimization problem (Section 4) and, finally, in sections 5 and 6, derive main results of the paper concerning random error bounds for the empirical solution $\hat{\rho}^{\varepsilon}.$ More precisely, we bound the squared $L_{2}(\Pi)$-distance $\|\hat{\rho}^{\varepsilon}-S\|_{L_{2}(\Pi)}^{2}$ and symmetrized Kullback-Leibler distance $K(\hat{\rho}^{\varepsilon};S)$ from $\hat{\rho}^{\varepsilon}$ to an arbitrary “oracle” $S\in{\cal S}$ and derive oracle inequalities for the squared $L_{2}(\Pi)$-error $\|\hat{\rho}^{\varepsilon}-\rho\|_{L_{2}(\Pi)}^{2}$ of the empirical solution $\hat{\rho}^{\varepsilon}.$ These results are first established for oracles $S$ of full rank and expressed in terms of certain characteristics of the operator $\log S$ (which is, essentially, a subgradient of the von Neumann entropy penalty used in (1.2)). Using simple techniques discussed in Section 4, we then develop the bounds for low rank oracles $S$ (such as the bounds of theorems 2 and 3) and also obtain oracle inequalities for so called “Gibbs oracles”. Note that the logarithmic factors involved in the bounds of theorems 2 and 3 (and in other results of this type discussed later in the paper), in particular, the factor $\log^{2}(mn),$ are related to the need to bound certain norms of $\log S$ for special oracles $S\in{\cal S}$ (as in Theorem 1). In the case of $\|S\|_{1}$-penalization, $\log S$ should be replaced with a version of ${\rm sign}(S)$ and one can avoid some of the logarithmic factors in this case.

Preliminaries: Distances in 𝒮,𝒮{\cal S}, Empirical Processes and Exponential Inequalities for Random Matrices

We will use noncommutative extensions of classical distances between probability distributions such as Kullback-Leibler and Hellinger distances. These extensions are common in quantum information theory (see Nielsen and Chuang (2000)). In particular, we will use Kullback-Leibler divergence between two states $S_{1},S_{2}\in{\cal S}$ defined as

We will also use a noncommutative version of Hellinger distance defined as follows. For any two states $S_{1},S_{2}\in{\cal S},$ let $F(S_{1},S_{2}):={\rm tr}\sqrt{S_{1}^{1/2}S_{2}S_{1}^{1/2}}.$ This quantity is called the fidelity of states $S_{1},S_{2}$ (see, e.g., Nielsen and Chuang (2000), p. 409). Then, a natural definition of the squared Hellinger distance is $H^{2}(S_{1},S_{2}):=2(1-F(S_{1},S_{2})).$ A remarkable property of this distance is that

where the supremum is taken over all POVMs $\{E_{i}\}$ (positive operator valued measures) and $p_{i}:={\rm tr}(S_{1}E_{i}),q_{i}:={\rm tr}(S_{2}E_{i}).$ [In the discrete case, a positive operator valued measure is a set $\{E_{i}\}$ of Hermitian nonnegatively definite matrices such that $\sum_{i}E_{i}=I$]. Thus, the quantum Hellinger distance is just the largest “classical” Hellinger distance between the probability distributions $\{p_{i}\},\{q_{i}\}$ of a “measurement” $\{E_{i}\}$ in the states $S_{1},S_{2}$ (see Nielsen and Chuang (2000), p. 412). The same property also holds for two other important “distances”, the trace distance $\|S_{1}-S_{2}\|_{1}$ and the Kullback-Leibler divergence $K(S_{1}\|S_{2})$ (see, e.g., Klauck et al (2007)). These properties immediately imply an extension of classical inequalities for these distances:

which implies (using that $2\sqrt{ab}\leq a/2+2b$)

2 Empirical processes bounds

We will use several inequalities for empirical processes indexed by a class of measurable functions ${\cal F}$ defined on an arbitrary measurable space $(S,{\cal A}).$ Let $X,X_{1},\dots,X_{n}$ be i.i.d. random variables in $(S,{\cal A})$ with common distribution $P.$ If ${\cal F}$ is uniformly bounded by a number $U,$ then Bousquet’s version of the famous Talagrand’s concentration inequality for empirical processes implies that, for all $t>0,$ with probability at least $1-e^{-t}$

where $\sigma^{2}:=\sup_{f\in{\cal F}}{\rm Var}_{P}(f(X)).$ We will also need a version of this bound for function classes that are not necessarily uniformly bounded. Such a bound was recently proved by Adamczak (2008). Let $F(x)\geq\sup_{f\in{\cal F}}|f(x)|,x\in S,$ be an envelope of the class. It follows from Theorem 4 of Adamczak (2008) that, there exists a constant $K>0$ such that for all $t>0$ with probability at least $1-e^{-t}$

In addition to this, we will need to bound the following expectation:

A usual approach to this problem is to use symmetrization inequality to replace the empirical process by a Rademacher process, and then to use Talagrand’s comparison (contraction) inequality (see, e.g., Ledoux and Talagrand (1991), Section 4.5) to get rid of the squares. This, however, would require the class ${\cal F}$ to be uniformly bounded by some $U>0,$ which is not too large. This approach is not sufficient in the case of subgaussian design considered in the last section. A more subtle approach has been developed in the recent years by Klartag and Mendelson (2005), Mendelson (2010) and it is based on generic chaining bounds.

Talagrand’s generic chaining complexity (see Talagrand (2005)) of a metric space $(T,d)$ is defined as follows. An admissible sequence $\{\Delta_{n}\}_{n\geq 0}$ is an increasing sequence of partitions of $T$ (i.e., each next partition is a refinement of the previous one) such that ${\rm card}(\Delta_{0})=1$ and ${\rm card}(\Delta_{n})\leq 2^{2^{n}},\ n\geq 1.$ For $t\in T,$ $\Delta_{n}(t)$ denotes the unique subset in $\Delta_{n}$ that contains $t.$ For a set $A\subset T,$ $D(A)$ denotes its diameter. Then, define the generic chaining complexity $\gamma_{2}(T;d)$ as

where the $\inf$ is taken over all admissible sequences of partitions.

where $K>0$ is a universal constant. Thus, the generic chaining complexity $\gamma_{2}(T;d)$ is a natural characteristic of the size of the Gaussian process $X(t),t\in T.$

Similar quantities can be also used to control the size of empirical processes indexed by a function class ${\cal F}.$ It is natural to define $\gamma_{2}({\cal F};L_{2}(P)),$ that is, $\gamma_{2}({\cal F};d),$ where $d$ is the $L_{2}(P)$-distance. Some other distances are also useful, for instance, the $\psi_{2}$-distance associated with the probability space $(S,{\cal A},P).$ Recall that, for a convex increasing function $\psi$ with $\psi(0)=0,$

(see van der Vaart and Wellner (1996), p. 95). If $\psi(u)=u^{p},u\geq 0,$ for some $p\geq 1,$ the corresponding $\psi$-norm is just the $L_{p}$-norm. Other important choices are functions $\psi_{\alpha}(t)=e^{t^{\alpha}}-1,t\geq 0,\alpha\geq 1,$ especially, $\psi_{2}$ that is related to subgaussian tails of $f$ and $\psi_{1}$ that is related to subexponential tails.

3 Noncommutative Bernstein type inequalities

We will need the following operator version of Bernstein’s inequality which is due to Ahlswede and Winter (2002) (and which has been already successfully used in the low rank recovery problems by Gross et al (2009), Gross (2009), Recht (2009)).

Bernstein’s inequality for operator valued r.v. Suppose that $\|X\|\leq U$ for some $U>0.$ Then

In fact, we will frequently use the following bound that immediately follows from the version of Bernstein’s inequality given above: for all $t>0,$ with probability at least $1-e^{-t}$

Moreover, it is possible to replace the $L_{\infty}$-bound $U$ on $\|X\|$ in the above inequality by bounds on the weaker $\psi_{\alpha}$-norms. Denote U_{X}^{(\alpha)}:=\Bigl{\|}\|X\|\Bigr{\|}_{\psi_{\alpha}},\ \alpha\geq 1.

Let $\alpha\geq 1.$ There exists a constant $C>0$ such that, for all $t>0,$ with probability at least $1-e^{-t}$

Note that, in the limit $\alpha\to\infty,$ inequality (3.3) coincides with (3.2) (up to a constant).

The following bounds are straightforward by simple matrix algebra:

To bound the expected value in the right hand side, we use independence of random variables $X_{1},\dots,X_{n}$ and Golden-Thompson inequality:

Let $M:=2(\log 2)^{1/\alpha}U_{X}^{(\alpha)}$ and assume that $\lambda\leq 1/M.$ Then

Let $\tau:=M\frac{2^{1/\alpha-1}}{(\log 2)^{1/\alpha}}\log^{1/\alpha}{\frac{M^{2}}{\sigma_{X}^{2}}}$ and suppose that $\lambda$ satisfies the condition $\lambda\tau\leq 1.$ Then, the following bound holds with some constant $C_{1}>0:$

Thus, we proved that there exist constants $C_{1},C_{2}>0$ such that, for all $\lambda$ satisfying the condition

It remains now to minimize the last bound with respect to all $\lambda$ satisfying (3.7) to get that, for some constant $K>0,$

Note that, in a standard way, one can deduce bounds on the expectation from the exponential bounds on tail probabilities. In particular, (3.1) implies that

Combining the last bounds with Talagrand’s concentration inequality leads to somewhat different versions of bounds (3.2) and (3.3) that can be better in some applications. Namely, denote

Similarly, combining the expectation bound (3.9) for $\alpha=1$ with Adamczak’s version of Talagrand’s inequality (see Section 3.2), we get that with probability at least $1-e^{-t}$

In principle, using bounds (3.10) and (3.11) in the proofs of the following sections instead of (3.2) and (3.3) provides a way to obtain probabilistic oracle inequalities with probabilities of the error decreasing exponentially with $m$ or $n$ (this is the way in which error bounds are written in the papers by Candes and Plan (2009) and Rohde and Tsybakov (2009)). We are not pursuing this approach here.

Approximation Error

A natural first step in the analysis of the problem is to study its version with the true risk instead of the empirical risk. The true risk with respect to the quadratic loss is equal to

and the goal is to study the error of approximation of $\rho$ by $\rho^{\varepsilon}$ depending on the value of regularization parameter $\varepsilon>0.$ The next propositions show that if there exists an oracle $S\in{\cal S}$ that provides a good approximation of the true state $\rho$ in a sense that $\|S-\rho\|_{L_{2}(\Pi)}$ is small, then $\rho^{\varepsilon}$ belongs to an $L_{2}(\Pi)$-ball around $S$ of small enough radius that can be controlled in terms of the operator norm $\|\log S\|$ or in terms of more subtle characteristics of the oracle $S.$ They also provide upper bounds on the approximation error $\|\rho^{\varepsilon}-\rho\|_{L_{2}(\Pi)}.$

We will first obtain a simple bound on $\|\rho^{\varepsilon}-S\|_{L_{2}(\Pi)}$ for an arbitrary oracle $S\in{\cal S}$ of full rank expressed in terms of the operator norm $\|\log S\|$ of its logarithm. For simplicity, we assume that $\|\log S\|=+\infty$ in the case when ${\rm rank}(S)<m$ (and $\log S$ is not defined). Note, however, that ${\rm tr}(S\log S)$ is well defined and finite even in the case when ${\rm rank}(S)<m.$

For all $S\in{\cal S},$ $\|\rho^{\varepsilon}-S\|_{L_{2}(\Pi)}\leq\|S-\rho\|_{L_{2}(\Pi)}+\sqrt{\varepsilon\|\log S\|}.$ This implies that

and, in particular, for $S=\rho,$ $\|\rho^{\varepsilon}-\rho\|_{L_{2}(\Pi)}^{2}\leq\varepsilon\|\log\rho\|.$

The following lemma is a simple corollary of Theorem V.3.3 in Bhatia (1996):

Proof of Proposition 3. Denote the penalized risk

This follows from the fact that the first term of the functional $L$ is differentiable since it is quadratic. The differentiability of the penalty term is based on Lemma 1 (it is enough to apply this lemma to the function $f(u)=u\log u$). Since $\rho^{\varepsilon}$ is the minimal point of $L$ in ${\cal S},$ we can conclude that, for an arbitrary $S\in{\cal S},$ $DL(\rho^{\varepsilon};S-\rho^{\varepsilon})\geq 0.$ This implies that

To conclude the proof, note that (4.2), the bound $\|S-\rho^{\varepsilon}\|_{1}\leq 2$ and Cauchy-Schwarz inequality imply that

Solving the last inequality with respect to $\|\rho^{\varepsilon}-S\|_{L_{2}(\Pi)}$ and using the fact that $K(S;\rho^{\varepsilon})\geq 0,$ yields the bound

which implies $\|\rho^{\varepsilon}-S\|_{L_{2}(\Pi)}\leq\|S-\rho\|_{L_{2}(\Pi)}+\sqrt{\varepsilon\|\log S\|},$ and the result follows.

To obtain more subtle bounds with approximation error of the order $O(\varepsilon^{2})$ instead of $O(\varepsilon),$ we introduce and use the following quantity

which will be called the alignment coefficient of $W.$ Similar quantities were used in the commutative case (Koltchinskii (2009)). Note that, for all constants $c,$

(since $\langle I_{m},U\rangle=0$ for all $U$ of zero trace). In addition, we have

and it is not hard to conclude that $a(W)\leq\|\bar{\cal K}^{-1/2}W\|_{2}.$ Moreover, in view of (4.3), for an arbitrary scalar $c,$

This shows that the size of $a(W)$ depends on how $W$ is “aligned” with the eigenspaces of the Gram matrix ${\cal K}.$ In a special case when, for all $A,$ $\|A\|_{L_{2}(\Pi)}=\|A\|_{2},$ the functions $\{\langle E_{j},\cdot\rangle:j=1,\dots,m^{2}\}$ form an orthonormal system in the space $L_{2}(\Pi)$ and the Gram matrix ${\cal K}$ is the identity matrix. In this case, we simply have the bound

In the next statement, we use the alignment coefficient $a(\log S)$ to control the $L_{2}(\Pi)$-distance $\|\rho^{\varepsilon}-S\|_{L_{2}(\Pi)}$ and the Kullback-Leibler “distance” $K(\rho^{\varepsilon};S)$ from the true solution $\rho^{\varepsilon}$ to an arbitrary oracle $S.$

In particular, it implies that $\|\rho^{\varepsilon}-\rho\|_{L_{2}(\Pi)}^{2}+\frac{\varepsilon}{2}K(\rho^{\varepsilon};\rho)\leq\frac{\varepsilon^{2}}{4}a^{2}(\log\rho).$ Moreover, the following bound also holds:

Proof. Our starting point is the relationship (4.2) from the proof of Proposition 3. It follows from the definition of $a(W),$ from (4.2) and from Cauchy-Schwarz inequality that

It remains to solve the last inequality for $\|S-\rho^{\varepsilon}\|_{L_{2}(\Pi)}$ to obtain the first bound of the proposition. The second bound is its special case with $S=\rho.$ To prove the third bound note that, by the definition of $\rho^{\varepsilon},$ for all $S\in{\cal S},$

where we used the fact that, by convexity of the function $S\mapsto{\rm tr}(S\log S),$

It remains to bound $\|\rho^{\varepsilon}-S\|_{L_{2}(\Pi)}$ from above using the first inequality of the proposition.

A consequence of propositions 3 and 4 is that

We will now provide versions of approximation error bounds for special types of oracles $S\in{\cal S}.$

There exists a numerical constant $C>0$ such that, for all $\varepsilon>0,$

Proof. Note that, for all matrices $W$ of rank $r$ “supported” in the space $L$ in the sense that $W=P_{L}WP_{L},$ we have

For $\delta\in(0,1),$ consider $S_{\delta}:=(1-\delta)S+\delta\frac{I_{m}}{m}.$ Then, using the fact that $a(W+cI_{m})=a(W),$ we get

Thus, it easily follows from Proposition 4 that

Taking $\delta=\varepsilon\wedge 1,$ this yields

Therefore $\Lambda(L)\leq\sup_{\|A\|_{L_{2}(\Pi)}\leq 1}\|A\|_{2}=\sup_{\|A\|_{2}\leq m}\|A\|_{2}=m.$ Also, in this case $\|X\|\leq\|X\|_{2}=1.$ Thus, Proposition 5 yields

Gibbs Oracles. Let $H$ be a Hermitian matrix (“a Hamiltonian”) and let $\beta>0.$ Consider the following density matrix (a “Gibbs oracle”):

For simplicity, assume in what follows that $\beta=1$ (in fact, one can always replace $H$ by $\beta H$) and denote $\rho_{H}:=\frac{e^{-H}}{{\rm tr}(e^{-H})}.$ Let $\gamma_{1}\leq\gamma_{2}\leq\dots\leq\gamma_{m}$ be the eigenvalues of $H$ and $e_{1},\dots,e_{m}$ be the corresponding eigenvectors. Let $L_{r}={\rm l.s.}(\{e_{1},\dots,e_{r}\})$ and $H_{\leq r}:=\sum_{j=1}^{r}\gamma_{j}(e_{j}\otimes e_{j}),\ \ H_{>r}:=\sum_{j=r+1}^{m}\gamma_{j}(e_{j}\otimes e_{j}).$ It is easy to see that

Under reasonable conditions on the spectrum of $H,$ the quantity $\delta_{r}(H)$ decreases fast enough when $r$ increases. Thus, $\rho_{H}$ can be well approximated by low rank matrices.

The next statement follows immediately from Proposition 4. Here the unknown density matrix $\rho$ is approximated by a Gibbs model with an arbitrary Hamiltonian. The error is controlled in terms of the $L_{2}(\Pi)$-distance between $\rho$ and the oracle $\rho_{H}$ and also in terms of the alignment coefficient $a(H_{\leq r})$ for a “low rank part” $H_{\leq r}$ of the Hamiltonian $H$ and the quantity $\delta_{r}(H).$

For all Hermitian nonnegatively definite matrices $H$ and for all $\varepsilon>0,$

Proof. We will use the last bound of proposition 4 with $S=\rho_{H_{\leq r}}.$ Note that

which can be easily bounded from above by

The result follows immediately (by the same argument as in the proof of Proposition 5).

Random Error Bounds and Oracle Inequalities

We now turn to the analysis of random error of the estimator $\hat{\rho}^{\varepsilon}.$ We obtain upper bounds on the $L_{2}(\Pi)$ and Kullback-Leibler distances of this estimator to an arbitrary oracle $S\in{\cal S}$ of full rank. In particular, this includes bounding the distances between $\hat{\rho}^{\varepsilon}$ and $\rho^{\varepsilon}.$ As a consequence, we will obtain oracle inequalities for the empirical solution $\hat{\rho}^{\varepsilon}.$ The size of both errors $\|\hat{\rho}^{\varepsilon}-S\|_{L_{2}(\Pi)}^{2}$ and $K(\hat{\rho}^{\varepsilon};S)$ will be controlled in terms of the squared $L_{2}(\Pi)$-distance $\|S-\rho\|_{L_{2}(\Pi)}^{2}$ from the oracle to the target density matrix $\rho$ and also in terms of such characteristics of the oracle as the norm $\|\log S\|$ or the alignment coefficient $a(\log S)$ that have been already used in the approximation error bounds of the previous section (see propositions 3, 4). However, in the case of the random error, we also need some additional quantities that describe the properties of the design distribution $\Pi$ and of the noise $\xi.$ These quantities are explicitly involved in the statements of the results below which makes these statements somewhat complicated. At the same time, it is easy to control these quantities in concrete examples and to derive in special cases the bounds that are easier to understand.

Assumptions on the design distribution $\Pi$. In this section, it will be assumed that $X$ is a random Hermitian $m\times m$ matrix and that, for some constant $U>0,$ $\|X\|\leq U.$ We will denote

Given $t>0,$ denote $t_{m}:=t+\log(2m),\ \ \tau_{n}:=t+\log\log_{2}(2n)$ and

We will start with a simple result in spirit of approximation error bound of Proposition 3.

There exists a constant $C>0$ such that, for all $S\in{\cal S}$ and for all $\varepsilon\geq 0,$ with probability at least $1-e^{-t}$

Note that this result holds for all $\varepsilon\geq 0,$ including the case of $\varepsilon=0$ that corresponds to the least squares estimator over the set ${\cal S}$ of all density matrices. The approximation error term $\|\log S\|\varepsilon$ in the bounds of Theorem 4 is of the order $O(\varepsilon)$ (as in Proposition 3) and the random error terms are, up to logarithmic factors, of the order $O(\frac{1}{\sqrt{n}})$ with respect to the sample size $n.$

Next we give a version of (5.4) in a special case when $S=\rho^{\varepsilon}.$ This provides bounds on random errors of estimation of the true penalized solution $\rho^{\varepsilon}$ by its empirical version $\hat{\rho}^{\varepsilon}$ both in the $L_{2}(\Pi)$ and in the Kullback-Leibler distances. Note that unlike the bounds for an arbitrary oracle $S,$ there is no dependence on the alignment coefficient $a(\log\rho^{\varepsilon})$ in this case. The result essentially shows that as soon as the true solution $\rho^{\varepsilon}$ is approximately low rank in the sense that $P_{L^{\perp}}\rho^{\varepsilon}P_{L^{\perp}}$ is “small” for a subspace $L$ of a “small” dimension $r$ and $\rho^{\varepsilon}$ provides a good approximation of the target density matrix $\rho,$ the empirical solution $\hat{\rho}^{\varepsilon}$ would also provide a good approximation of $\rho$ and it would be approximately low rank.

Remark. In the case when the noise is not necessarily bounded, but $\|\xi\|_{\psi_{1}}<+\infty,$ the results still hold with the following simple modifications. In bounds (4), (4), (5.3) and in the definition of $\varepsilon_{n,m},$ the term $(c_{\xi}U\vee U^{2})\frac{t_{m}}{n}$ is to be replaced by

In the bounds of theorems 5 and 6, the term $c_{\xi}U\frac{\tau_{n}\vee t_{m}}{n}$ is to be replaced by

We will provide a detailed proof of Theorem 5. The proof of Theorem 4 is its simplified version. The proof of Theorem 6 relies on the bounds derived in the proof of Theorem 5. It is also possible to derive the oracle inequalities of Theorem 5 from Theorem 6 and from the approximation error bounds of Proposition 4. Throughout the proofs below, $C,C_{1},\dots$ are numerical constants whose values might be different in different places.

By necessary conditions of extrema in the convex optimization problem (1.2), $DL_{n}(\hat{\rho}^{\varepsilon};\hat{\rho}^{\varepsilon}-S)\leq 0,$ which implies

By a simple algebra similar to what has been already used in the proofs of propositions 3, 4, we get the following bound:

Since $\varepsilon|{\rm tr}((\hat{\rho}^{\varepsilon}-S)\log S)|\leq\varepsilon a(\log S)\|\hat{\rho}^{\varepsilon}-S\|_{L_{2}(\Pi)},$ we get from (5.8) that

We need to bound the empirical processes in the right hand side of bound (5.9). We will do it in several steps by bounding each term separately.

Step 1. To bound the first term note that

Step 2. The second term can be written as

We use again the noncommutative version of Bernstein’s inequality to show that with probability at least $1-e^{-t}$

Step 3. We turn now to bounding the third term in the right hand side of (5.9). It is easy to decompose it as follows:

Applying the noncommutative version of Bernstein’s inequality one more time, we have that with probability at least $1-e^{-t}$

Hence, with probability at least $1-2e^{-t},$

To bound the second term in the right hand side of (5), denote

Clearly, \biggl{|}\frac{1}{n}\sum_{j=1}^{n}\xi_{j}\langle\hat{\rho}^{\varepsilon}-S,{\cal P}_{L}X_{j}\rangle\biggr{|}\leq\alpha_{n}(\|\hat{\rho}^{\varepsilon}-S\|_{L_{2}(\Pi)}). To control $\alpha_{n}(\delta),$ we use Talagrand’s concentration inequality for empirical processes. It implies that, for all $\delta>0,$ with probability at least $1-e^{-s},$

We will make the bound on $\alpha_{n}(\delta)$ uniform in $\delta\in[Un^{-1},2U].$ To this end, we apply bound (5.11) for $\delta=\delta_{j}=2^{-j+1}U,\ j=0,1,\dots$ and with $s=\tau_{n}:=t+\log\log_{2}(2n).$ The union bound and the monotonicity of $\alpha_{n}(\delta)$ with respect to $\delta$ implies that with probability at least $1-e^{-t}$ for all $\delta\in[Un^{-1},2U]$

Let us assume in what follows that $\|\hat{\rho}^{\varepsilon}-S\|_{L_{2}(\Pi)}\geq Un^{-1}$ since another case is even easier to handle.

We now substitute the bounds of steps 1–3 in the right hand side of (5.9) to get the following inequality that holds with some constant $C>0$ and with probability at least $1-5e^{-t}:$

Under the assumption $\varepsilon\geq D\varepsilon_{n,m}$ with a sufficiently large constant $D>0,$ it is easy to get that

and, under the same assumption that $\varepsilon\geq D\varepsilon_{n,m}$ with a sufficiently large constant $D>0,$

Combining bounds (5.15) and (5.16) with (5.14) yields

with some constant $C>0.$ It follows from the last inequality that

where $A:=\frac{\varepsilon}{2}a(\log S)+C\sigma_{\xi}\beta(L)\sqrt{\frac{mr+\tau_{n}}{n}}$ and

If $\frac{\varepsilon}{4}K(\hat{\rho}^{\varepsilon};S)\geq B,$ then $\|\hat{\rho}^{\varepsilon}-S\|_{L_{2}(\Pi)}^{2}\leq A^{2},$ which, in view of (5.18), implies

Otherwise, we have $\|\hat{\rho}^{\varepsilon}-S\|_{L_{2}(\Pi)}^{2}\leq A^{2}+2A\sqrt{B}+B-\frac{\varepsilon}{4}K(\hat{\rho}^{\varepsilon};S),$ which, for all $\lambda>0,$ implies

In both cases, by the definitions of $A$ and $B$ and by elementary algebra, one can easily get the bound

that holds with probability at least $1-5e^{-t}$ and with a sufficiently large constant $C.$ To replace the probability $1-5e^{-t}$ by $1-e^{-t},$ it is enough to replace $t$ by $t+\log 5$ and to adjust the values of constants $C,D$ accordingly.

Proof of Theorem 4. We get back to bound (5.8) in the proof of Theorem 5. This time, we bound the term ${\rm tr}((\hat{\rho}^{\varepsilon}-S)\log S)$ in (5.8) in a slightly different way

which leads to the following bound (instead of bound (5.9)):

To bound the empirical processes in the right hand side, we again use the bounds of steps 1–3 in the proof of Theorem 5. The bound of Step 1 yields

and it follows from the bound of Step 2 that

Instead of more complicated derivation of Step 3, we now use noncommutative and classical Bernstein’s inequalities to get that with probability at least $1-2e^{-t}$

Using these inequalities, we derive from (5.20) that with some numerical constant $C>0$ and with probability at least $1-4e^{-t},$

Proof of Theorem 6. Note that similarly to $\rho^{\varepsilon},$ $\hat{\rho}^{\varepsilon}$ is also a matrix of full rank and $\log\hat{\rho}^{\varepsilon}$ is well defined. By necessary conditions of extrema in convex problems (1.2) and (4.1), we have $DL_{n}(\hat{\rho}^{\varepsilon};\hat{\rho}^{\varepsilon}-\rho^{\varepsilon})\leq 0$ and $DL(\rho^{\varepsilon};\hat{\rho}^{\varepsilon}-\rho^{\varepsilon})\geq 0.$ Subtracting the second inequality from the first one yields

By a simple algebra already used in the proof of Theorem 5, this easily leads to the following bound:

We use the bounds of steps 1–3 of the proof of Theorem 5 with $S=\rho^{\varepsilon}$ to control each term in the right hand side of (5.23). Substituting these bounds in (5.23), we get the following inequality that holds with probability at least $1-5e^{-t}:$

Arguing exactly as in the proof of Theorem 5, we can simplify (5.24) to get

It is easy now to solve this for $\|\hat{\rho}^{\varepsilon}-\rho^{\varepsilon}\|_{L_{2}(\Pi)}$ and to derive the following explicit bound on the random error that holds with probability at least $1-5e^{-t}$ and with some numerical constant $C>0:$

Assume that $X$ is sampled at random from this basis. Recall that in this case, for all matrices $A,$ $\|A\|_{L_{2}(\Pi)}^{2}=m^{-2}\|A\|_{2}^{2}.$ Obviously, $\|e_{i}\otimes e_{i}\|=1,\ i=1,\dots,m$ and, for all $i<j,$

Note that, if $X=e_{i}\otimes e_{i},i=1,\dots,m,$ then $|Xv|^{2}=|e_{i}\langle e_{i},v\rangle|^{2}=|\langle e_{i},v\rangle|^{2}.$ If $X=\frac{1}{\sqrt{2}}(e_{i}\otimes e_{j}+e_{j}\otimes e_{i}),i<j,$ then

and, similarly, if $X=\frac{i}{\sqrt{2}}(e_{i}\otimes e_{j}-e_{j}\otimes e_{i}),i<j,$ then also |Xv|^{2}=\frac{1}{2}\Bigl{(}|\langle e_{j},v\rangle|^{2}+|\langle e_{i},v\rangle|^{2}\Bigr{)}. Therefore, for $|v|=1,$

which implies that $\sigma_{X}\leq\frac{\sqrt{3}}{\sqrt{m}}.$ By a similar simple computation, $\sigma_{X\otimes X}\leq\frac{4}{\sqrt{m}}.$ Now we can derive the following corollary of Theorem 5. Let

and let $\varepsilon=D\varepsilon_{n,m}$ for a sufficiently large constant $D>0.$

There exists a numerical constant $C>0$ such that the following holds. For all $t>0,$ for all $\lambda>0,$ for all sufficiently large $D$ and for $\varepsilon=D\varepsilon_{n,m},$ for all matrices $S\in{\cal S}$ of rank $r,$ with probability at least $1-e^{-t},$

This immediately follows from Theorem 5 since, in the case under consideration, $\beta(L)=1,$ $\sigma_{X}\leq 3^{1/2}m^{-1/2},$ $\sigma_{X\otimes X}\leq 4m^{-1/2},$ $U=1.$ Note also that in this case $\Lambda(L)=m$ (recall the definition of $\Lambda(L)$ given before Proposition 5) and

Suppose now that $S\in{\cal S}$ is an arbitrary oracle of rank $r.$ Then there exists a subspace $L$ of dimension $r$ such that $P_{L^{\perp}}SP_{L^{\perp}}=0.$ We will use bound (5) for $S_{\delta}:=(1-\delta)S+\delta\frac{I_{m}}{m},$ where $\delta=\varepsilon\wedge 1,$ as we did in the proof of Proposition 5. As in this proof, we have, for some constant $C_{1}>0,$

Substituting these bounds in (5) (with $S$ replaced by $S_{\delta}$) and bounding $\|S_{\delta}-\rho\|_{L_{2}(\Pi)}^{2}$ in terms of $\|S-\rho\|_{L_{2}(\Pi)}^{2}$ and $\|S_{\delta}-S\|_{L_{2}(\Pi)}^{2}$ (similarly to what was done in the proof of Proposition 5), it is easy to derive (1) from (5). Note that we can drop the term $\sigma_{\xi}^{2}\frac{mr}{n}$ since it is dominated by $(\sigma_{\xi}^{2}\vee 1)\frac{rmt_{m}}{n}\log^{2}(mn).$

Similarly, it is easy to obtain another corollary where the $L_{2}(\Pi)$-error of estimator $\hat{\rho}^{\varepsilon}$ is controlled in terms of Gibbs oracles. Recall the notations at the end of Section 4 and also denote $\Gamma_{r}:=\|H_{\leq r}\|_{2}^{2}=\sum_{k=1}^{r}\gamma_{k}^{2}.$

There exists a numerical constant $C>0$ such that the following holds. For all $t>0,$ for all $\lambda>0,$ for all sufficiently large $D$ and for $\varepsilon=D\varepsilon_{n,m},$ for all Hermitian matrices $H$ and for all $r\leq m,$ with probability at least $1-e^{-t},$

implying that $\|X\|=m^{-1/2}$ and $U=m^{-1/2}.$ To state a corollary of Theorem 5 in this case, we take $\varepsilon:=D\varepsilon_{n,m},$ where

The following results are similar to corollaries 1 and 2.

There exists a numerical constant $C>0$ such that the following holds. For all $t>0,$ for all $\lambda>0,$ for all sufficiently large $D>0$ and for $\varepsilon=D\varepsilon_{n,m},$ for all matrices $S\in{\cal S}$ of rank $r,$ with probability at least $1-e^{-t},$

There exists a numerical constant $C>0$ such that the following holds. For all $t>0,$ for all $\lambda>0,$ for all sufficiently large $D$ and for $\varepsilon=D\varepsilon_{n,m},$ for all Hermitian matrices $H$ and for all $r\leq m,$ with probability at least $1-e^{-t},$

Note that the bounds of corollaries 1-4 can be also proved in the case when the noise is unbounded, in particular, Gaussian (see the remark after Theorem 6). For the Pauli basis, this immediately leads to Theorem 3 stated in the Introduction.

Oracle Inequalities: Subgaussian Design Case

In addition to this, assume that, for some constant $b_{2}>0,$

A Hermitian random matrix $X$ satisfying the above conditions will be called a subgaussian matrix. Moreover, if $X$ also satisfies the condition

The following is a version of a well known fact (see, e.g., Rudelson and Vershynin (2010), Proposition 2.4).

Let $X$ be a subgaussian $m\times m$ matrix. Then, there exists a constant $B>0$ such that

Take $\varepsilon=1/2.$ Using standard bounds for Orlicz norms of a maximum (see, e.g., van der Vaart and Wellner (1996), Lemma 2.2.2), we get that, with some constants $C_{1},C_{2},B>0,$

Below, we give oracle inequalities and random error bounds in the subgaussian design case. We will use the following notations. Given $t>0,$ let

Also, denote $c_{\xi}:=\|\xi\|_{\psi_{2}}\log\frac{\|\xi\|_{\psi_{2}}}{\sigma_{\xi}}$ and let

(clearly, we assume here that the noise has a bounded $\psi_{2}$-norm).

There exist constants $C>0,c>0$ such that the following holds. For all $t>0$ and $\lambda>0$ such that $\tau_{n}\leq c\lambda^{2}n,$ for all $S\in{\cal S}$ and for all $\varepsilon\in,$ with probability at least $1-e^{-t}$

We now turn to more subtle oracle inequalities that take into account low rank properties of oracles $S\in{\cal S}.$

Similarly to the previous section, we also derived bounds on the random error $\|\hat{\rho}^{\varepsilon}-\rho^{\varepsilon}\|_{L_{2}(\Pi)}^{2}.$

We will give only the proof of Theorem 8.

Proof. It follows the lines of the proof of Theorem 5 very closely. The main changes are in the bounds of steps 1–3 of this proof that have to be modified in the subgaussian design case. The rest of the proof is straightforward.

In Step 1, we have to bound the following quantity:

To this end, we will study the empirical process

where ${\cal F}_{\delta}:=\{\langle S_{1}-S_{2},\cdot\rangle:S_{1},S_{2}\in{\cal S},\|S_{1}-S_{2}\|_{L_{2}(\Pi)}\leq\delta\}.$ Clearly,

Our goal is to obtain an upper bound on $\Delta_{n}(\delta)$ uniformly in $\delta\in[(m/n)^{1/2},2b_{2}].$ First we use a version of Talagrand’s concentration inequality for empirical processes indexed by unbounded functions due to Adamczak (see subsection 3.2). It implies that with some constant $C>0$ and with probability at least $1-e^{-t}$

Here we used the following bounds on the uniform variance and on the envelope of the function class ${\cal F}_{\delta}^{2}:$ for the uniform variance, with some constant $c>0,$

by the equivalence properties of the norms in Orlicz spaces. For the envelope,

for some constants $c_{1},c_{2},c_{3}>0,$ where we used well known inequalities for maxima of random variables in Orlicz spaces (see, e.g., Lemma 2.2.2 in van der Vaart and Wellner (1996)).

with some constant $c>0.$ It follows from (6.1) that the $\psi_{1}$ and $\psi_{2}$-norms of functions from the class ${\cal F}_{\delta}$ can be bounded from above by a constant times the $L_{2}(P)$-norm. As a result,

and the following bound holds for Talagrand’s generic chaining complexities:

and it easily follows from Talagrand’s generic chaining bound that, for some constant $C>0,$

It follows from (6.10), (6.11), (6.12) and (6.13) that

Substituting this bound in (6.14) yields that, for some constant $C>0,$

and combining (6.15) with (6.9) gives that with probability at least $1-e^{-t}$

It is easy to make bound (6.16) uniform in $\delta\in[(m/n)^{1/2},2b_{2}]$ by a simple discretization argument (as we did in Step 3 of the proof of Theorem 5). This leads to the following result: with probability at least $1-e^{-t},$ for all $\delta\in[(m/n)^{1/2},2b_{2}],$

where $\tau_{n}=t+\log\log_{2}(2n).$ Thus, with the same probability and with a proper choice of constant $C>0$

provided that $\|\hat{\rho}^{\varepsilon}-S\|_{L_{2}(\Pi)}\in[(m/n)^{1/2},2b_{2}].$

Similarly to Step 2 of the proof of Theorem 5, we have to bound the expression

and Proposition 2 with $\alpha=1.$ Note that

with some constants $c_{1},c_{2}>0.$ Finally, note that

since, for $S,\rho\in{\cal S},$ $\|S-\rho\|_{1}\leq 2$ and $\|S-\rho\|\leq 2.$ Using the fact $\|\hat{\rho}^{\varepsilon}-S\|_{1}\leq 2,$ Proposition 2 and the previous bounds imply that with probability at least $1-e^{-t}$ and with some constants $C_{1},C_{2},C>0,$

We now modify the bounds of Step 3 of the proof of Theorem 5. We need to bound the following expression:

By Proposition 2, it is easy to show that with probability at least $1-e^{-t},$

Hence, with probability at least $1-e^{-t},$

The remaining term $\frac{1}{n}\sum_{j=1}^{n}\xi_{j}\langle\hat{\rho}^{\varepsilon}-S,{\cal P}_{L}X_{j}\rangle$ is bounded exactly as in Step 3 of the proof of Theorem 5 with the use of Adamczak’s (2008) version of Talagrand’s concentration inequality. This leads to the following bound: with probability at least $1-e^{-t},$

For simplicity, we state the next corollaries (similar to corollaries 1 and 2) only in the case of subgaussian isotropic design. Recall that in this case $\|\cdot\|_{L_{2}(\Pi)}=\|\cdot\|_{2}$ and $\beta(L)=1.$

There exist numerical constants $C>0,c>0$ such that the following holds. For all $t>0$ and $\lambda>0$ such that $\tau_{n}\leq c\lambda^{2}n,$ for all sufficiently large $D>0$ and for $\varepsilon=D\varepsilon_{n,m},$ for all matrices $S\in{\cal S}$ of rank $r,$ with probability at least $1-e^{-t},$