Sparse Phase Retrieval via Sparse PCA despite Model
Misspecification: A Simplified and Extended Analysis

arXiv:1712.04106v2 [] 13 Dec 2017

Yan Shuo Tan

∗

December 14, 2017

Abstract
We consider the problem of high-dimensional misspecified phase retrieval. This is where
we have an s-sparse signal vector x∗ in Rn , which we wish to recover using sampling vectors
a1 , . . . , am , and measurements y1 , . . . , ym , which are related by the equation f (hai , x∗ i) = yi .
Here, f is an unknown link function satisfying a positive correlation with the quadratic function.
This problem was recently analyzed in [24], which provided recovery guarantees for a two-stage
algorithm with sample complexity m = O(s2 log n). In this paper, we show that the first stage
of their algorithm suffices for signal recovery with the same sample complexity, and extend
the analysis to non-Gaussian measurements. Furthermore, we show how the algorithm can be
generalized to recover a signal vector x∗ efficiently given geometric prior information other than
sparsity.

1

Introduction

1.1

Phase retrieval and sparse phase retrieval

The phase retrieval problem is that of solving a system of quadratic equations
|hai , xi2 | = yi ,

i = 1, 2, . . . , m

(1.1)

where ai ∈ Rn (or Cn ) are known sampling vectors, yi > 0 are observed measurements, and x ∈ Rn
(or Cn ) is the decision variable. Over the last half a decade, there has been great interest in constructing and analyzing algorithms with provable guarantees, with much success in the case where
the sampling vectors are independently drawn from either a real or complex standard Gaussian
distribution. The notable approaches include lifting and convex relaxation (PhaseLift) [9], convex
relaxation in the natural parameter space (PhaseMax ) [16, 3, 17], gradient descent [8, 10, 35, 32],
stochastic gradient descent [29, 20], and prox-linear methods [14]. The best of these methods
have been proved to accurately recover the true underlying signal x∗ so long as the number of
measurements m is proportional to the signal dimension n.
Naturally, researchers have tried to replicate this success in the high-dimensional regime. In this
setting, it is assumed that the true signal x∗ is s-sparse, and one would like to estimate x∗ accurately
with much fewer measurements than the ambient dimension, in analogy with what is possible for
sparse linear regression. Work in this direction has mostly comprised straightforward adaptations of
∗

Department of Mathematics, University of Michigan, yanshuo@umich.edu.

1

algorithms for unconstrained phase retrieval: Both PhaseLift and PhaseMax have been be adapted
by adding l1 regularizers to their respective objective functions [25, 18]. Meanwhile, the gradient
descent schemes Truncated Wirtinger Flow and Truncated Amplitude Flow have been adapted to
alternate gradient steps with either soft- or hard-thresholding [6, 33, 28]. These methods have been
mostly shown to accurately recover x∗ with sample complexity m = O∗ (s2 ).

1.2

Single index models and model agnostic recovery

Phase retrieval is an example of a single index model. In this more general setting, the measurements
and the sampling vectors are related by the formula
f (hai , x∗ i) = yi ,

i = 1, 2, . . . , m

(1.2)

where f is a (possibly random) link function. Such models have been studied for some time in
the statistics community (see [21] and the references therein). Classically, it is assumed that the
link function f is unknown to the observer, and it is of interest to estimate both x∗ (the index
parameter) and f . Standard theoretical results in this body of work include asymptotic minimax
rates of various estimators.
In this paper, we take a slightly different approach to the problem. We continue to assume
that f is unknown, but now treat x∗ as the only parameter of interest. On the other hand, we are
interested in algorithms that are provably efficient from both a statistical as well as a computational
point of view. Furthermore, we want our algorithms to be able to exploit a sparsity prior and
thus work in the high-dimensional regime. The motivation for such an approach comes from the
observation that real data almost never obeys a precise algebraic relationship. In other words, the
neat relationships we postulate, such as (1.1), are often misspecified.
Recently, Plan and Vershynin [27] made significant progress on this problem in the setting of
misspecified linear regression. They showed that if Cov(g, f (g)) 6= 0, then the standard Lasso
algorithm for sparse linear regression is able to estimate x∗ accurately up to scaling, and with a
sample complexity of O(s log n), the same order as that in the case of no model misspecification.
Here, g ∼ N(0, 1) is a standard Gaussian random variable.
In the misspecified phase retrieval (MPR) setting, the first work was done by Neykov, Wang
and Liu [24]. They proposed a two stage algorithm that works as follows. First, they form the
reweighted sample covariance matrix
m

Σ̂ :=

1 X
yi (ai aTi − In ),
m

(1.3)

i=1

and apply the standard SDP relaxation of Sparse PCA to this matrix. Next, they use the leading
eigenvector of the solution to formulate a Lasso-type program. The solution to this program is
their final estimate. The assumptions they make are that
µ = µ(g, f ) := Cov(g2 , f (g)) > 0,

kf (g)kψ1 ≤ C,

(Af,g )

under which, they were able to prove that the algorithm recovers x∗ accurately when given m =
O∗ (s2 ) independent standard Gaussian sampling vectors. Again, this is the same order as the
guarantees for sparse phase retrieval in the case of no misspecification.

2

1.3

Contributions

The contribution of this short paper is twofold. First, we prove that Sparse PCA, the first step
of the algorithm proposed in [24], suffices to recover the signal vector x∗ accurately with the same
sample complexity as the full two-step algorithm given in their paper. We provide a simplified and
more flexible analysis that is adapted from [26]. This analysis has the further benefit of generalizing
to the case where the prior assumption on x∗ is not that it is sparse, but that it lies in a geometric
set K.
Second, we provide a guarantee for Sparse PCA to recover x∗ accurately when the sampling
vectors are not Gaussian, but are instead drawn from distributions with independent subgaussian
entries. In particular, we show that the method works for Rademacher random variables. Although
this is a realistic sampling model, to our knowledge, it has not been analyzed in any prior work
on phase retrieval. This guarantee requires two conditions. Unsurprisingly, we require the link
function f to satisfy a correlation condition similar to (Af,g ), but adapted to the given subgaussian
distribution. Second, we require x∗ to have entries of equal magnitude over its support. This
second condition is relatively stringent, but can probably be relaxed in future work.

1.4

Notation

We shall use boldface letters to denote vectors and matrices. If A and B are real matrices of the
same dimensions, we let hA, Bi := Tr(AT B) denote the standard inner product. kAk and kAkF
will denote the operator and Frobenius norm of A respectively, while kAk1 and kAk∞ will denote
the entrywise l1 and l∞ norms respectively. For a random variable X and α > 0, we let kXkψα
denote its ψα norm.1 If a is a random vector, then ai refers to an i-th independent copy of a, while
(a)i refers to the i-th coordinate of a. C and c are used to denote constants that may change from
line to line.

2

Main results

We shall work with the single index model (1.2). We assume that the sampling vectors a1 , . . . , am
are independent copies of a random vector a satisfying the following distributional assumption:
Assumption 2.1 (Sampling vector distribution). The coordinates of a are independent copies of a
random variable Z that is centered, symmetric, of unit variance, and with subgaussian norm kZkψ2
bounded by an absolute constant C.
For convenience, we shall hide the dependence on C in our results and in our analysis. We do
not assume that we know the link function f . The algorithm we propose to estimate x∗ is the
following.
1

This is a tail decay condition. For more information, see Appendix A.

3

Algorithm 1 Sparse PCA for MPR
Input: Measurements y1 , . . . , ym , sampling vectors a1 , . . . , am , sparsity level s.
Output: An estimate x̂ for x∗ .
1: Compute Σ̂ as defined in (1.3).
2: Let X̂ be the solution to
max hX, Σ̂i subject to
X0

3:

Tr(X) = 1, kXk1 ≤ s.

(2.1)

Let x̂ be the leading eigenvector to X̂.

This program is precisely the SDP relaxation of Sparse PCA proposed by d’Aspremont et al.
[11] and later analyzed by Amini and Wainwright [1] and Berthet and Rigollet [5]. These two papers
analyzed the performance of the algorithm as applied to sparse principal component detection in
the spiked covariance model. Since the matrix Σ̂ does not follow this model a priori, one requires
further analysis to show that the algorithm succeeds.
In [24], the authors propose using the Lagrangian version of this program as the first step of their
algorithm. Their analysis (see Lemma C.1. therein) shows that when the sampling vectors follow
a Gaussian distribution, one can obtain a constant error approximation to x∗ using O(s2 log n)
samples. Using our methods, we prove a stronger version of this guarantee.
Theorem 2.2 (Sparse recovery for Gaussian measurements). Suppose a is a standard Gaussian in
Rn , and suppose Assumption (Af,g ) holds. Then there is an absolute constant C such that for any
s-sparse, unit norm signal x∗ and any ǫ, δ > 0, the output x̂ to Algorithm 1 satisfies kx̂ − x∗ k2 ≤ ǫ
with probability at least 1 − δ so long as the sample size m satisfies
)
(

s2 log(n/δ) + log4 (s/δ) s log(n/δ)
.
, ,
m ≥ C max
µ(f, g)2 ǫ4
δ log2 m
Although this result is not entirely novel, we prove it in a different way compared to [24]. This
method is simple and amenable to generalization to the situation where the sampling vectorsP
are not
1
Gaussian. In the non-Gaussian case, we first fix the the sparsity parameter s. Let Z̄s := s si=1 Zi
and rs,Z := (Z1 − Z̄s , . . . , Zs − Z̄s ) denote the mean of s independent copies of Z and the vector of
residuals respectively. With this notation, we make the assumption:
√
√
(Af,Z,s )
µ(f, Z, s) := Cov(( sZ̄s )2 , f ( sZ̄s )) > 0,
√
√
2
σ(f, Z, s) := Cov(krs,Z k2 , f ( sZ̄s )) ≤ 0, kf ( sZ̄s )kψ1 ≤ C.
Furthermore, we say that a unit norm signal vector x∗ is admissible if it has entries of equal
magnitude across its support. In other words, there is a index set I ⊂ [n] of cardinality |I| ≤ s,
such that

± √1
j∈I
|I|
(x∗ )j =
0
otherwise.
Using this definition, we have the following analogue of Theorem 2.2.

4

Theorem 2.3 (Sparse recovery for non-Gaussian measurements). There is an absolute constant
C such that the following holds. Fix a sparsity parameter s, suppose x∗ is admissible and suppose
Assumption (Af,Z,s ) holds. Then for any ǫ, δ > 0, the output x̂ to Algorithm 1 satisfies kx̂−x∗ k2 ≤ ǫ
with probability at least 1 − δ so long as the sample size m satisfies

Cs2 log(n/δ) + log4 (s/δ)
Cs C log(n/δ)
.
(2.2)
+
+
m≥
2
4
µ(f, Z, s) ǫ
δ
log2 m
Note that when Z is standard Gaussian, Assumption (Af,Z,s ) reduces to Assumption (Af,g ). To
√
see this, observe that for any s, sZ̄ is a standard Gaussian random variable, while σ(f, g, s) = 0 by
the independence property of orthogonal Gaussian marginals. This fact points to the assumption
being the right generalization of (Af,g ).
Furthermore, it is intuitive that the second condition should hold whenever Z has a reasonable
distribution and when µ(f, Z, s) > 0: if f is positively correlated with the magnitude of Z̄, then it
should be negatively correlated with the norm of the residual vector. Indeed, this can be shown to be
true whenever Z is a Rademacher random variable. We thus have a simpler result for Rademacher
random variables:
Corollary 2.4 (Sparse recovery for Rademacher measurements). There is an absolute constant C
such that the following holds. Fix a sparsity parameter s, suppose x∗ is admissible, let Z denote
√
a Rademacher random variable. Suppose µ(f, Z, s) > 0 and kf ( sZ̄s )kψ1 ≤ C. Then for any
ǫ, δ > 0, the output x̂ to Algorithm 1 satisfies kx̂ − x∗ k2 ≤ ǫ with probability at least 1 − δ so long
as the sample size m satisfies (2.2).
In the Gaussian setting, the recovery guarantee continues to hold even if we relax our constraint
√
on x∗ slightly and instead assume that kx∗ k1 ≤ s. This condition is geometric: it can equivalently
√
expressed as x∗ ∈ K, where K = sB1n is the l1 norm ball. It is thus an interesting theoretical
question to ask whether one can construct efficient algorithms for estimating x∗ that exploit prior
knowledge that x∗ ∈ K for a general convex set K.
There has been some work on proving statistical efficiency guarantees for various algorithms.
In the misspecified linear regression setting, Plan and Vershynin showed that the K-Lasso succeeds whenever the number of measurements m is of the order w(K)2 , where w(K) denotes the
Gaussian width of K [27]. In the phase retrieval setting, Soltanolkotabi showed that Projected
Amplitude Flow also succeeds whenever m & w(K)2 . On the other hand, it is hard to remark on
the computational efficiency of these methods, because this depends on the properties of the set K.
The final main result of this paper is a guarantee of a similar spirit.
Theorem 2.5 (Recovery using general geometric constraints). Suppose x∗ xT∗ ∈ K, where K is a
convex subset of the space of unit trace PSD matrices in Rn×n . Suppose a is a standard Gaussian
in Rn , and suppose Assumption Af,g holds. Then for any ǫ, δ > 0, the output x̂ to Algorithm 2
satisfies kx̂ − x∗ k2 ≤ ǫ with probability at least 1 − δ so long as the sample size m satisfies

C w(K)2 + log4 (1/δ) + log m(γ1 (K, k·k) + log(1/δ))
C
(2.3)
+ .
m≥
2
4
µ(f, g) ǫ
δ
Here, w(K) and γ1 (K, k·k) respectively denote the Gaussian width of K and its γ1 -functional with
respect to the operator norm, while C is a universal constant.
5

Organization of paper and outline of proof strategy
We prove Theorem 2.2 and Theorem 2.3 in Section 3. The strategy we take comprises two steps.
First, we compute the expected objective function used in Algorithm 1, and show that it has sufficient curvature on the feasible set around the ground truth matrix, x∗ xT∗ . This shows that feasible
solutions having large expected objective value must also be close to x∗ xT∗ . This computation is
done in Section 4.
Next, we argue that the empirical objective function is uniformly close to the expected objective
function with high probability, so that a solution to the SDP program actually has large expected
objective value. This is proved in Section 5. Finally, we use the same strategy for Theorem 2.5, but
replace the objective function concentration analysis with a more sophisticated chaining argument.
Due to its more technical nature, we defer the details to Appendix B.

3

Proof of results for sparse recovery

Proof of Theorem 2.2. Let X be the solution to Algorithm 1. Since x∗ xT∗ is also feasible for the
program, we have by optimality that
0 ≤ hX − x∗ xT∗ , Σ̂i = hX − x∗ xT∗ , Σi + hX − x∗ xT∗ , Σ̂ − Σi.

(3.1)

Using Lemma 4.3, the first term satisfies the bound
hX − x∗ xT∗ , Σi ≤ −

µ(f, g)
kx∗ xT∗ − Xk2F .
2

For the second term, we use Hölder’s inequality to write
hX − x∗ xT∗ , Σ̂ − Σi ≤ X − x∗ xT∗

1

kΣ̂ − Σk∞ .

Next, we have by assumption that
x∗ xT∗ 1

=

m
X

|(x∗ )i (x∗ )j | = kx∗ k21 ≤ s.

i,j=1

Meanwhile, by construction, we also know that kXk1 ≤ s. Rearranging (3.1), we therefore get
µ(f, g)
kx∗ xT∗ − Xk2F ≤ 2skΣ̂ − Σk∞ .
2
Using Proposition 5.1 to bound the right hand side, we get
p

Cs
log(n/δ) + log2 (s/δ)
√
.
kx∗ xT∗ − Xk2F ≤
µ(f, g) m
If x̂ denotes the leading eigenvector of X, we use Davis-Kahan’s eigenvector perturbation theorem [12] to conclude that kx̂ − x∗ k22 satisfies the same bound. Finally, we plug in our assumption
on m to show that this bound is less than ǫ2 .
Proof of Theorem 2.3. Exactly the same as for the Theorem 2.2.
6

√
Proof of Corollary 2.4. Observe that krs,Z k22 + ( sZ̄s )2 = kak22 = s. We have
√
σ(f, Z, s) = Cov(f ( sZ̄s ), krs,Z k22 )
√
√
= Cov(f ( sZ̄s ), s − ( sZ̄s )2 )
√
√
= −Cov(f ( sZ̄s ), ( sZ̄s )2 ) = µ(f, Z, s).
The corollary now follows from Theorem 2.3.

4

Objective function in expectation

In this section, we compute expressions for the expected reweighted covariance matrix Σ = EΣ̂.
Note that we may also write
Σ = Ey(aaT − In ).
Lemma 4.1 (Expected covariance for Gaussian distribution). Suppose a ∼ N(0, In ). Then for any
x∗ ∈ S n−1 , we have
Σ = µ(f, g)x∗ xT∗ .
Proof. Decompose a = ha, x∗ ix∗ +a⊥ , where a⊥ is the projection of a to the orthogonal complement
of x∗ . Using this, we write
E{yaaT } = E{f (ha, x∗ i)(ha, x∗ ix∗ + a⊥ )(ha, x∗ ix∗ + a⊥ )T }

= E{f (ha, x∗ i)ha, x∗ i2 x∗ xT∗ } + E{f (ha, x∗ i)a⊥ (a⊥ )T }

+ E{f (ha, x∗ i)ha, x∗ ix∗ (a⊥ )T } + E{f (ha, x∗ i)ha, x∗ ia⊥ xT∗ }.

Because a is a standard Gaussian, ha, x∗ i and a⊥ are independent. This means that the third and
fourth terms in this sum are zero. Furthermore, the second term can be written as the product of
two expectations E{f (ha, x∗ i)} and E{a⊥ (a⊥ )T }. We now use standard computations for Gaussians
to continue writing
E{y(aaT − In )} = E{f (g)g 2 }x∗ xT∗ + E{f (g)}(In − x∗ xT∗ ) + E{f (g)}In
= µ(f, g)x∗ xT∗ .

This completes the proof.
Lemma 4.2 (Expected covariance for non-Gaussian distributions). Suppose a is a random vector
in Rn that satisfies Assumption 2.1. Let 2 ≤ s ≤ n be an integer, and let x∗ be an admissible signal
vector. We have
σ(f, Z, s)
(PI − x∗ xT∗ ).
Σ = µ(f, Z, s)x∗ xT∗ −
s−1

c
Proof. Let PI and P⊥
I denote the orthogonal projections to the coordinates in I and I respectively.
Then PI a and P⊥
I a are independent. Using a similar calculation as in the previous lemma, we see
⊥
⊥
⊥
that PI ΣP⊥
=
P
I
I ΣPI = PI ΣPI = 0. We may hence assume WLOG that s = n and I = [n]. By
the symmetry of the distribution of a, we may also assume that x∗ = √1n , where 1 is the all ones
vector.

7

Next, notice that ha, x∗ i is invariant to permutation of the coordinate indices. Meanwhile, the
distributions of a⊥ and a are both symmetric with respect to such transformations. Let Q be a
permutation matrix. Then
QΣQT = E{f (ha, x∗ i)Qa(Qa)T }

= E{f (hQa, x∗ i)Qa(Qa)T }

= E{f (ha, x∗ i)a(a)T }.
In other words, we have
QΣQT = Σ.

(4.1)

One can check that a matrix satisfying (4.1) for all permutation matrices Q must have the same
value for all diagonal entries, and the same value for all off-diagonal entries. In other words, Σ
must be of the form
1
α
(4.2)
Σ = 11T + β(In − 11T )
n
n
for some values of α and β.
Let us now compute the values of α and β using the fact that x∗ = √1n . We have
α = xT Σx∗ = µ(f, Z, n).
Next, we apply traces to (4.2) to get
α + (n − 1)β = Tr(Σ) = E{f (ha, x∗ i)Tr(aaT − In )}.
Observe further that
E{f (ha, x∗ i)Tr(aaT − In )} = E{f (ha, x∗ i)(kak22 − n)} = σ(f, Z, n) + µ(f, Z, n).
As such, we have β =

σ(f,Z,n)
n−1

as we wanted.

Lemma 4.3 (Curvature of objective function). Suppose the hypotheses of Lemma 4.1 (respectively
Lemma 4.2) hold. For any X  0 such that Tr(X) = 1, we have
hΣ, x∗ xT∗ − Xi ≥

µ
kx∗ xT∗ − Xk2F ,
2

(4.3)

where µ = µ(f, g) (respectively µ = µ(f, Z, s)).
Proof. We shall prove the case where the hypotheses of Lemma 4.2 hold. The other case is similar
and even easier. First, observe that
hΣ, x∗ xT∗ i = µ(f, Z, s)hx∗ xT∗ , x∗ xT∗ i = µ(f, Z, s)kx∗ k42 .
We also have
σ(f, Z, s)
hPI − x∗ xT∗ , Xi
s−1
σ(f, Z, s)
= µ(f, Z, s)hx∗ xT∗ , Xi +
Tr(X RI ∩x⊥ )
∗
s−1
T
≤ µ(f, Z, s)hx∗ x∗ , Xi.

hΣ, Xi = µ(f, Z, s)hx∗ xT∗ , Xi +

8

Here, the last inequality follows from the fact that X is positive semidefinite, which implies that
any partial trace has to be non-negative.
Now, the assumptions on X also imply that kXkF ≤ 1 = kx∗ k2 . We can thus combine our
calculations to get
hΣ, x∗ xT∗ − Xi ≥ µ(f, Z, s)kx∗ k42 − µ(f, Z, s)hx∗ xT∗ , Xi

µ(f, Z, s) 
kx∗ xT∗ kF + kXk2F − 2hx∗ xT∗ , Xi
≥
2
µ(f, Z, s)
=
kx∗ xT∗ − Xk2F .
2
This completes the proof.

5

Concentration of objective function

The goal of this section is to prove the following concentration theorem for the reweighted sample
covariance matrix Σ̂.
Proposition 5.1 (Concentration of sample matrix). There is a universal constant C so that the
following holds. Fix a sparsity parameter s, let a be defined using Assumption 2.1. Suppose Assumption (Af,Z,s ) holds, and let x∗ be a unit norm vector. If a is non-Gaussian, further assume
that x∗ is admissible. Then for any δ > 0, we have
p
C( log(n/δ) + log2 (s/δ))
√
kΣ̂ − Σk∞ ≤
m
with probability at least 1 − δ, provided m ≥ C max{s/δ, log(n/δ) log 2 m}.
Proof. Without loss of generality, assume that the support of x∗ is contained in the first s coordinates. Let Ps denote the projection to the first s coordinates. We write
o
n
⊥
⊥
(5.1)
kΣ̂ − Σk∞ = max kPs (Σ̂ − Σ)Ps k∞ , kPs (Σ̂ − Σ)P⊥
k
,
kP
(
Σ̂
−
Σ)P
k
s ∞
s
s ∞ ,

and bound each of the terms on the right separately.
For the first term, we shall use the fact that each entry is the mean of m i.i.d. ψ1/2 random
variables (see Appendix A). This tail decay gives us a relatively strong large deviation inequality,
which we can use together with a union bound. In more detail, let 1 ≤ k, l ≤ s. Then
(Σ̂ − Σ)kl =

m
i
1 Xh
(ai )k (ai )l f (hai , x∗ i) − E{(ai )k (ai )l f (hai , x∗ i)} .
m
i=1

We now use Proposition A.6 followed by Proposition A.5 twice to get
k(a)k (a)l f (ha, x∗ i) − E{(a)k (a)l f (ha, x∗ i)}kψα . k(a)k (a)l f (ha, x∗ i)kψ1/2
. k(a)k (a)l kψ1 kf (ha, x∗ i)kψ1

. k(a)k kψ2 k(a)l kψ2 kf (ha, x∗ i)kψ1 .
9

Each of the terms in the product on the right hand side is bounded by an absolute constant by
assumption. As such, the quantity on the left is also bounded by an absolute constant. We may
thus use Proposition A.9 to see that
√
√
P{|(Σ̂ − Σ)kl | > t/ m} ≤ 2 exp(−c t)
for t > 0 large enough. Pick t ∼ log2 (s/δ). Then we can take a union bound over all s2 choices of
k and l to get
log2 (s/δ)
√
kPs (Σ̂ − Σ)Ps k∞ .
m
with probability at least 1 − δ/4.
We next bound the other two quantities in (5.1) via a conditioning argument similar to that in
[24]. The key idea is to condition on the probability 1 − δ/4 event over which the three statements
in Lemma 5.3 hold, and to observe that this event is independent of the random variables (ai )k for
1 ≤ i ≤ m, s < k ≤ n. Hence, conditioning on the event does not alter the joint distribution of this
set of random variables.
We consider a typical entry in Ps (Σ̂ − Σ)P⊥
s , which is of the form
m

1 X
(ai )k (ai )l f (hai , x∗ i),
m
i=1

1 ≤ k ≤ s, s < l ≤ n.

(5.2)

Fixing all randomness apart from (ai )l for all indices 1 ≤ i ≤ m, s < l ≤ n, we can use Hoeffding’s
inequality (Proposition
A.2) to conclude that for each l, (5.2) is a subgaussian random variable
P
2
2
with variance m12 m
(a
i=1 i )k f (hai , x∗ i) . By the second statement of Lemma 5.3, this is bounded
by C/m, so that
)
(
m
t
1 X
≤ 2 exp(−ct2 )
(5.3)
(ai )k (ai )l f (hai , x∗ i) > √
P
m
m
i=1
p
Choosing t ∼ log(n/δ) and taking a union bound over s < l ≤ n gives
r
log(n/δ)
⊥
kPs (Σ̂ − Σ)Ps k∞ .
m
with probability at least 1 − δ/4.
⊥
Finally, each entry of P⊥
s (Σ̂ − Σ)Ps is of the form
m


1 X
f (hai , x∗ i) (ai )k (ai )l − E{(ai )k (ai )l } ,
m
i=1

s < k, l ≤ n.

(5.4)

We again fix all randomness apart from (ai )l for all indices 1 ≤ i ≤ m, s < l ≤ n. Observe that
(ai )k (ai )l − E{(ai )k (ai )l }, s < k, l ≤ n, are centered subexponential random variables. We may
thus use Bernstein’s inequality (Proposition A.3) together with the second and third statements of
Lemma 5.3 to obtain the tail bound:
)
(


√ 
m


t
1 X
2 t m
f (hai , x∗ i) (ai )k (ai )l − E{(ai )k (ai )l } > √
≤ 2 exp −c min t ,
(5.5)
P
m
log m
m
i=1

10

Once again, choosing t ∼

p

log(n/δ) and taking a union bound over s < k, l ≤ n gives
r
log(n/δ)
⊥
,
kPs (Σ̂ − Σ)Ps k∞ .
m

with probability at least 1 − δ/4 provided that m & log(n/δ) log 2 m.
Remark 5.2. When a is a standard Gaussian, [24] gave the bound
p
C log(n/δ)
√
kΣ̂ − Σk∞ ≤
m
with roughly the same tail probability. Hence, the only price to having more distributional generality is the additional log2 (s/δ) term in the numerator.
Lemma 5.3. Let the hypotheses of Proposition 5.1 hold. There is an absolute constant C such that
the following holds. Let I denote the support of x∗ . Then for any δ > 0, so long as m ≥ Cs/δ, the
following three statements hold simultaneously with probability at least 1 − δ/4.
1.

m
X
i=1

f (hai , x∗ i)2 ≤ Cm.

2. max
k∈I

m
X
(ai )2k f (hai , x∗ i)2 ≤ Cm.
i=1

3. max f (hai , x∗ i) ≤ C log m.
1≤i≤m

Proof. By Assumption (Af,Z,s ), we know that kf (hai , x∗ i)kψ1 is bounded by an absolute constant.
As such, Proposition A.4 implies that both its second and fourth moments are also bounded.
Furthermore, we have
Var(f (hai , x∗ i)2 ) ≤ E{f (hai , x∗ i)4 } ≤ C,
where C is an absolute constant. Using Chebyshev’s inequality together with the second moment
bound, we thus get
)
(m
X
C
f (hai , x∗ i)2 ≥ m(C + t) ≤
P
.
(5.6)
mt2
i=1

We can use the same argument together with a union bound over k ∈ I to get
)
(
m
X
Cs
(ai )2k f (hai , x∗ i)2 ≥ m(C + t) ≤
P max
.
k∈I
mt2

(5.7)

i=1

Finally, we again use the union bound and the subexponential tail bound to get


P max f (hai , x∗ i) ≥ t log m ≤ 2m exp(−ct log m) = 2m1−ct .
1≤i≤m

(5.8)

Choose t to be any fixed constant in (5.6) and (5.7), and choose t to be a constant larger than
2/c in (5). Then each of these probability bounds is of the order O(1/m), so that m & s/δ suffices
for all three statements to hold with probability at least 1 − δ/4.
11

6

Conclusion and discussion

In this paper, we have analyzed the problem of misspecified phase retrieval, and improved upon the
work of Neykov et al. in [24]. In particular, we have shown that the first stage of their algorithm
suffices for signal recovery with the same sample complexity, and extended the analysis to nonGaussian measurements. Furthermore, we showed how the algorithm can be generalized to recover
a signal vector x∗ efficiently given geometric prior information other than sparsity.
Experts in compressed sensing may have observed that while the sample complexity for algorithms for misspecified linear regression scales linearly with the sparsity parameter, our sample
complexity bounds for misspecified phase retrieval scale instead with the square of the parameter. In [24], the authors showed numerical evidence that this discrepancy is due to the statistical
inefficiency of the algorithm, and not merely a slackness in the mathematical analysis.
This s2 scaling is also observed in all other efficient algorithms for sparse phase retrieval, and
it is an open question whether there exist computationally efficient algorithms that can do better.
The authors of [24] conjecture that the answer is in the negative. This is supported by results by
Berthet and Rigollet, who show that computationally efficient algorithms for the related problem
of detecting sparse principal components, using O(s2−ǫ ) samples for any ǫ > 0, will lead to computationally efficient algorithms for solving hard instances of the planted clique problem [5, 4]. This
is widely conjectured to be impossible.
It will also be interesting to investigate whether there is slackness in the sample complexity
bound for signal recovery using general geometric constraints (Theorem 2.5). In particular, I do
not know how to bound γ1 (K, k·k) where K is the set of unit trace PSD matrices X with kXk1 ≤ s.
Hence, it is not yet clear whether Theorem 2.2 can be derived from Theorem 2.5.
Finally, the literature on high-dimensional signal recovery from non-Gaussian measurements is
still fairly limited. In this work, we have proved a recovery guarantee for admissible signal vectors
in the case of misspecified phase retrieval. Hopefully, this guarantee can be extended to larger
classes of signal vectors in the near future.

Acknowledgements
I would like to thank Roman Vershynin and Shahar Mendelson for helpful discussions. Part of this
manuscript was written on a visit to UC Irvine supported by U.S. Air Force Grant FA9550-18-10031.

References
[1] Amini, A. A., and Wainwright, M. J. High-dimensional analysis of semidefinite relaxations
for sparse principal components. Annals of Statistics 37, 5 B (2009), 2877–2921.
[2] Bahmani, S., and Romberg, J. Anchored Regression: Solving Random Convex Equations
via Convex Programming. Preprint, available at http://arxiv.org/abs/1702.05327.
[3] Bahmani, S., and Romberg, J. Phase Retrieval Meets Statistical Learning Theory: A
Flexible Convex Relaxation. Preprint, available at http://arxiv.org/abs/1610.04210.
[4] Berthet, Q., and Rigollet, P. Complexity Theoretic Lower Bounds for Sparse Principal
Component Detection. JMLR: Workshop and Conference Proceedings 30, 2012 (2013), 1–21.
12

[5] Berthet, Q., and Rigollet, P. Optimal detection of sparse principal components in high
dimension. Annals of Statistics 41, 4 (2013), 1780–1815.
[6] Cai, T., Li, X., and Ma, Z. Optimal rates of convergence for noisy sparse phase retrieval
via thresholded wirtinger flow. Annals of Statistics 44, 5 (2016), 2221–2251.
[7] Candès, E. J., Li, X., and Soltanolkotabi, M. Phase retrieval from coded diffraction
patterns. Applied and Computational Harmonic Analysis 39, 2 (2015), 277–299.
[8] Candès, E. J., Li, X., and Soltanolkotabi, M. Phase Retrieval via Wirtinger Flow:
Theory and Algorithms. IEEE Transactions on Information Theory 61, 4 (2015), 1985–2007.
[9] Candès, E. J., Strohmer, T., and Voroninski, V. PhaseLift: Exact and stable signal
recovery from magnitude measurements via convex programming. Communications on Pure
and Applied Mathematics 66, 8 (2013), 1241–1274.
[10] Chen, Y., and Candes, E. Solving random quadratic systems of equations is nearly as easy
as solving linear systems. In Advances in Neural Information Processing Systems 28. 2015,
pp. 739–747.
[11] D’Aspremont, A., Bach, F., and Ghaoui, L. E. Optimal Solutions for Sparse Principal
Component Analysis. Solutions 9 (2007), 1269–1294.
[12] Davis, C., and Kahan, W. M. The rotation of eigenvectors by a perturbation. III. SIAM
Journal on Numerical Analysis 7, 1 (1970), 1–46.
[13] Dirksen, S. Tail bounds via generic chaining. Electronic Journal of Probability 20 (2015),
1–29.
[14] Duchi, J. C., and Ruan, F. Solving (most) of a set of quadratic equalities: Composite
optimization for robust phase retrieval. Preprint, available at http://arxiv.org/abs/1705.02356.
[15] Ganti, R., Rao, N., Willett, R. M., and Nowak, R. Learning Single Index Models in
High Dimensions. Preprint, available at http://arxiv.org/abs/1506.08910.
[16] Goldstein, T., and Studer, C. PhaseMax: Convex Phase Retrieval via Basis Pursuit.
Preprint, available at http://arxiv.org/abs/1610.07531.
[17] Hand, P., and Voroninski, V. An Elementary Proof of Convex Phase Retrieval in
the Natural Parameter Space via the Linear Program PhaseMax. Preprint, available at
http://arxiv.org/abs/1611.03935.
[18] Hand, P., and Voroninski, V. Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space. Preprint, available at
http://arxiv.org/abs/1611.05985.
[19] Jaganathan, K., Oymak, S., and Hassibi, B. Sparse phase retrieval: Convex algorithms
and limitations. IEEE International Symposium on Information Theory - Proceedings (2013),
1022–1026.

13

[20] Jeong, H., and Güntürk, C. S. Convergence of the randomized Kaczmarz method for
phase retrieval. Preprint, available at http://arxiv.org/abs/1706.10291.
[21] Kuchibhotla, A. K., and Patra, R. K. Efficient Estimation in Single Index Models
through Smoothing splines. Preprint, available at https://arxiv.org/abs/1708.00145.
[22] Ledoux, M., and Talagrand, M. Probability in Banach Spaces: Isoperimetry and Processes. Springer Science & Business Media, 1991.
[23] Ma, T., and Wigderson, A. Sum-of-squares lower bounds for sparse PCA. In Advances in
Neural Information Processing Systems 28. 2015, pp. 1612–1620.
[24] Neykov, M., Wang, Z., and Liu, H. Agnostic estimation for misspecified phase retrieval
models. In Advances in Neural Information Processing Systems 29. 2016, pp. 4089–4097.
[25] Ohlsson, H., Yang, A., Dong, R., and Sastry, S. Cprl – an extension of compressive
sensing to the phase retrieval problem. In Advances in Neural Information Processing Systems
25. 2012, pp. 1367–1375.
[26] Plan, Y., and Vershynin, R. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach. IEEE Transactions on Information Theory 59, 1
(2013), 482–494.
[27] Plan, Y., and Vershynin, R. The generalized lasso with non-linear observations. IEEE
Transactions on Information Theory 62, 3 (2016), 1528–1537.
[28] Soltanolkotabi, M. Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization.
Preprint, available at
http://arxiv.org/abs/1702.06175.
[29] Tan, Y. S., and Vershynin, R. Phase Retrieval via Randomized Kaczmarz: Theoretical
Guarantees. Preprint, available at http://arxiv.org/abs/1706.09993.
[30] van der Vaart, A. W., and Wellner, J. A. Weak Convergence and Empirical Processes.
Springer Series in Statistics. Springer New York, New York, NY, 1996.
[31] Vershynin, R.
High-Dimensional Probability.
Book draft,
https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.html.

available

at

[32] Wang, G., Giannakis, G. B., and Eldar, Y. C. Solving Systems of Random Quadratic
Equations via Truncated Amplitude Flow. IEEE Transactions on Signal Processing 65, 8 (may
2016), 1961–1974.
[33] Wang, G., Zhang, L., Giannakis, G. B., Akcakaya, M., and Chen, J.
Sparse Phase Retrieval via Truncated Amplitude Flow.
Preprint, available at
http://arxiv.org/abs/1611.07641.
[34] Wei, K. Solving systems of phaseless equations via Kaczmarz methods: a proof of concept
study. Inverse Problems 31, 12 (Dec 2015), 125008.
[35] Zhang, H., and Liang, Y. Reshaped wirtinger flow for solving quadratic system of equations.
In Advances in Neural Information Processing Systems 29. 2016, pp. 2622–2630.
14

A

Results on ψα random variables

In this section, we collect some standard definitions and results on ψα random variables that help
us give streamlined proofs for our main theorems. These are collated from [22], [30], [31], and [23].
Definition A.1 (Orlicz norms). Let ψ : R+ → R+ be a convex, increasing function with ψ(0) = 0.
Define the Orlicz norm of a random variable X with respect to ψ as
kXkα := inf{λ > 0 : E{ψ(|X|/λ)} ≤ 1}.
Equipped with this norm, the space of random variables with finite norm forms a Banach space,
called an Orlicz space.
We are especially interested in the Orcliz spaces corresponding to ψα for α > 0. These are
defined as follows. When α ≥ 1, we set ψα (x) := exp(xα ) − 1. When 0 < α ≤ 1, this function is no
longer convex, so we convexify it by fiat, setting ψα (x) := exp(xα ) − 1 for x ≥ x(α) large enough,
and taking ψα to be linear on [0, x(α)]. If some random variable X has a finite ψα norm kXkψα ,
we say that it is a ψα random variable.
Readers will probably be familiar with ψ2 and ψ1 Orcliz spaces. These correspond to subgaussian
and subexponential random variables respectively (see [31] for more details). For these two classes
of random variables, we have the well-known Hoeffding’s and Bernstein’s inequalities.
Proposition A.2 (Hoeffding’s inequality). Let X1 , . . . , Xm be independent, centered, subgaussian
random variables. Then for every t ≥ 0, we have
!
)
( m
X
ct2
,
Xi ≤ 2 exp − Pm
P
2
i=1 kXi kψ2
i=1

where c > 0 is an absolute constant.

Proposition A.3 (Bernstein’s inequality). Let X1 , . . . , Xm be independent, centered, subexponential random variables. Then for every t ≥ 0, we have
)!
)
(
( m
X
t2
t
,
Xi ≤ 2 exp −c min Pm
P
2 , max kX k
i
i ψ1
i=1 kXi kψ1
i=1
where c > 0 is an absolute constant.

In this paper however, it will be useful for us to consider Orlicz spaces in full generality. This
is because we will need to work with ψ1/2 random variables, for which many of the standard
concentration inequalities do not hold. Nonetheless, we still have the following.
Proposition A.4 (Characterization of ψ1/2 RVs). Let X be a real-valued random variable. Then
the following properties are equivalent. The parameters Ci > 0 appearing in these properties differ
from each other by at most an absolute contant factor.
1. The tails of X satisfy
 p

P{|X| ≥ t} ≤ 2 exp − t/C1 .
15

2. The moments of X satisfy

kXkp = (E|X|p )1/p ≤ C2 p2 .

3. The ψ1/2 norm of X satisfies
kXkψ1/2 ≤ C3 .
Proof. Same as in the case of ψ1 and ψ2 . See [31].
We have the following further properties.
Proposition A.5 (Products, Lemma 8.5 in [23]). Let X and Y be ψα random variables for some
α > 0. Then XY is a ψα/2 random variable with ψα/2 norm satisfying
kXY kψα/2 ≤ Cα kXkψα kY kψα .
Here, Cα is an absolute constant depending only on α.
Proposition A.6 (Centering). Let X be a ψα random variable for some α > 0. Then
kX − EXkψα ≤ 2kXkψα .
Proof. We have kX − EXkψα ≤ kXkψα + kEXkψα . Now check the definition of the norm to verify
that kEXkψα ≤ kXkψα .
Proposition A.7 (Sums, Theorem 6.21 in [22]). Let 0 < α ≤ 1, and let X1 , . . . , Xm be a sequence
of independent, centered ψα random variables. Then
!
m
m
X
X
Xi + max |Xi |
.
≤ Cα E
Xi
i=1

1≤i≤m

i=1

ψα

ψα

Here, Cα is an absolute constant depending only on α.
Proposition A.8 (Maxima, Lemma 2.2.2 in [30]). Let 0 < α ≤ 1, and let X1 , . . . , Xm be independent, centered ψα random variables. Then
max |Xi |

1≤i≤m

ψα

≤ Cα ψα−1 (m) max kXi kψα .
1≤i≤m

Here, Cα is an absolute constant depending only on α.
Proposition A.9 (Bernstein-type inequality for ψ1/2 RVs). Let X1 , . . . , Xm be an independent,
P
centered ψ1/2 random variables. There is an absolute contant C such that Sm := √1m m
i=1 Xi is a
ψ1/2 random variable with ψ1/2 norm satisfying
kSm kψ1/2 ≤ C max kXi kψ1/2 .
1≤i≤m

In particular, if max1≤i≤m kXi kψ1/2 is bounded above by a constant, for every t ≥ 0, we have
P{|Sm | ≥ t} ≤ 2 exp(−
16

p

t/C).

Proof. This follows more or less immediately from the last two propositions. First, notice that


2 1/2
m
m
X
X
√
Xi  ≤ C m max kXi kψ1/2
Xi ≤ E
E
1≤i≤m

i=1

i=1

Here, the first inequality is an application of Jensen’s inequality, and the second uses the moment
bound in Proposition A.4. Next, we compute ψα−1 (m) = (log(m + 1))2 , and use Proposition A.8,
we get
max |Xi |

1≤i≤m

ψα

≤ C(log m)2 max kXi kψα .
1≤i≤m

Finally, plug these two bounds into the inequality given by Proposition A.7, and note that
√
log(m + 1)/ m ≤ 5. This completes the proof of the first statement. The tail bound follows from
Proposition A.4.

B

Recovery using general geometric signal constraints

The goal of this section is to prove Theorem 2.5, and to collate the necessary theoretical apparatus
for doing so. First, we state the algorithm we propose for estimating x∗ given general geometric
constraints. We call this algorithm K-PCA.
Algorithm 2 K-PCA for MPR
Input: Measurements y1 , . . . , ym , sampling vectors a1 , . . . , am .
Output: An estimate x̂ for x∗ .
1: Compute Σ̂ as defined in (1.3).
2: Let X̂ be the solution to
max hX, Σ̂i subject to X ∈ K.
X0

3:

(B.1)

Let x̂ be the leading eigenvector to X̂.

This can be seen as a tensorized version of the 1-bit sensing algorithm proposed in [26]. Our
analysis will be also be similar to that in [26], but we will require a more general concentration
result (Lemma B.3) that is derived via chaining. We introduce the requisite definitions as follows.
Let (T , d) be a metric space. A sequence T = (Tk )k∈Z+ of subsets of T is called admissible if
k
|T0 | = 1, and |Tk | ≤ 22 for all k ≥ 1. For any 0 < α < ∞, we define the γα functional of (T , d) to
be
∞
X
γα (T , d) := inf sup
2k/α d(t, Tk ).
(B.2)
T

t∈T k=0

When (T , d) is a subset of Rn with the Euclidean metric, Talagrand’s comparison theory tells us
that γ2 (T , d) ≍ w(T ), where w(T ) is the Gaussian width of T (see [22, 31]). Also note that for
any positive constant c > 0, we have γα (T, cd) = cγα (T , d). We shall use this fact later.
Now, let d1 and d2 be two metrics on T . We say that a process (Yt ) has mixed tail increments
with respect to (d1 , d2 ) if there are constants c and C such that for all s, t ∈ T , we have the bound
√
(B.3)
P(|Ys − Yt | ≥ c( ud2 (s, t) + ud1 (s, t))) ≤ Ce−u .
17

Lemma B.1 (Suprema of mixed tail processes, Theorem 5, [13]). If (Yt )t∈T has mixed tail increments, then there is a constant C such that for any u ≥ 1, with probability at least 1 − e−u ,
√
(B.4)
sup|Yt − Yt0 | ≤ C(γ2 (T , d2 ) + γ1 (T , d1 ) + udiam(T , d2 ) + udiam(T , d1 )).
t∈T

Let us return to our situation, where we have a subset K of unit trace PSD matrices in Rn×n .
Fix x∗ xT∗ , and real numbers z1 , . . . , zm . We define a process on the set K as follows. Let a1 , . . . , am
be standard Gaussians. For each X ∈ K, we set
P
T
T
YX = h m
i=1 zi (ai ai − In ), X − x∗ x∗ i.
We claim the following.

Lemma B.2 (Process increments).
The process YX has mixed tail increments with respect to
Pm 2 1/2
′
(d1 , d2 ), where d2 (X, X ) = ( i=1 zi ) kX − X′ kF , and d1 (X, X′ ) = maxi |zi | · kX − X′ k.

Proof. Fix X, X′ ∈ K, and for convenience, denote H = X − X′ . Then
YX − YX′ =
=

m
X
i=1

m
X
i=1

=


zi aTi Hai − E{aTi Hai }
zi

n
X
j=1

n
m X
X
i=1 j=1



λj hai , vj i2 − E{hai , vj i2 }



zi λj hai , vj i2 − 1 ,

P
T
where H = m
i=1 λi vi vi is the eigendecomposition of H. Next, observe that by the independence
of orthogonal Gaussian marginals, {(hai , vj i2 − 1) : 1 ≤ i ≤ m, 1 ≤ j ≤ n} are independent,
centered subexponential random variables with bounded subexponential norm. We may thus apply
Bernstein’s inequality to get
(
)!
t2
t
P{|YX − YX′ | ≥ t} ≤ 2 exp −c min Pm Pn
.
2 2,
i=1
j=1 zi λj maxi,j |zi λj |
P
Finally, observe that nj=1 zj2 = kHk2F and max1≤j≤n |zj | = kHk. One can now check that (B.3) is
satisfied with respect to our chosen d1 and d2 .

Lemma B.3 (Uniform deviation bound). Let a1 , . . . , am be independent standard Gaussians, and
suppose that Assumption (Af,g ) holds. Let K be a convex subset of the space of unit trace PSD
matrices in Rn×n . For any ǫ, δ > 0, if m satisfies the lower bound (2.3), then with probability at
least 1 − δ, we have
sup hΣ̂ − Σ, X − x∗ xT∗ i ≤ ǫ2 ,
X∈K

Proof. The proof of this concentration bound follows the same strategy as that in [27]. A priori,
the process we are trying to control has heavy tails. To overcome this, we will use a decoupling
argument together with conditioning.
18

denote projection
For each X ∈ K, denote H = X − x∗ xT∗ for convenience. Let Px∗ and Px⊥
∗
onto x∗ and its orthogonal complement respectively. We can then write
, Hi
(Σ̂ − Σ)Px⊥
(Σ̂ − Σ)Px∗ , Hi + hPx⊥
hΣ̂ − Σ, Hi = hPx∗ (Σ̂ − Σ)Px∗ , Hi + 2hPx⊥
∗
∗
∗
= hPx∗ (Σ̂ − Σ)Px∗ , Hi + 2hPx⊥
Σ̂Px∗ , Hi + hPx⊥
Σ̂Px⊥
, Hi.
∗
∗
∗

(B.5)

We shall bound the three terms on the right separately.
Recalling that Px∗ = x∗ xT∗ , we see that the first term can be written as

hPx∗ (Σ̂ − Σ)Px∗ , Hi = xT∗ (Σ̂ − Σ)x∗ xT∗ Hx∗
"
#
m
1 X
2
2
=
yi (hai , x∗ i − 1) − E{y(hai , x∗ i − 1)} xT∗ Hx∗ .
m
i=1

xT∗ Hx∗

Notice that
≤ 1. Meanwhile, the term in the square brackets is the average of independent,
centered, ψ1/2 random variables. Using Proposition A.9, we have a probability at least 1 − δ/4
event over which the following bound holds:
sup hPx∗ (Σ̂ − Σ)Px∗ , Hi ≤

X∈K

C log(1/δ)2
√
.
m

(B.6)

For the third term in (B.5), we write
m

P x⊥
Σ̂Px⊥
=
∗
∗


1 X 
T
a
)(P
a
)
−
P
yi (Px⊥
⊥
⊥
i
i
x∗
x∗ .
∗
m
i=1

ai are independent, we may decouple them. In other words, we replace each ai
Since yi and Px⊥
∗
with a fully independent copy ãi . We can therefore write
D P
 E

m
1
T −P
,
Hi
=
hPx⊥
Σ̂P
ã
)
ã
)(P
(P
y
⊥
⊥
⊥
⊥
i
i
i
x∗
x∗ , H
x∗
x∗
i=1
m
∗
E
D P
m
1
T − I ), P HP
y
(
ã
ã
= m
⊥
⊥
i
i
i
n
x∗
x∗
i=1

Fix the randomness with respect to a1 , . . . , am , y1 , . . . , ym , conditioning on the probability
1 − δ/4 event that the three statements in Lemma B.4 hold. With respect to the ãi ’s, Lemma B.2
shows us that this process indexed over X ∈ K has mixed tails. Furthermore, since K is a subset
of the nuclear norm ball, its diameter with respect to both the Frobenius and operator norms is
bounded by 2. Lemma B.1 then gives us another probability 1 − δ/4 event over which

m

p
C X 2 1/2 
≤
,
Hi
Σ̂P
γ
(K,
k·k
)
+
y
)
sup hPx⊥
(
log(1/δ)
+ max |yi |(γ1 (K, k·k) + log(1/δ))
⊥
2
x∗
i
2
∗
1≤i≤m
m
X∈K
i=1
!
p
γ2 (K, k·k2 ) + log(1/δ) log m(γ1 (K, k·k) + log(1/δ))
√
.
(B.7)
+
≤C
m
m

Finally, for the second term in (B.5), we again decouple, writing
E
D P
m
1
T,H
a
)
y
ha
,
x
ix
(P
hPx⊥
Σ̂P
,
Hi
=
i
∗ ∗
x∗
x⊥
i=1 i i
m
∗
∗
D P
E
m
1
T,H
= m
ã
)
y
ha
,
x
ix
(P
⊥
∗ ∗
x∗ i
i=1 i i
D P
E
m
1
= m
Hx
y
ha
,
x
iã
,
P
⊥
∗ .
∗ i
x∗
i=1 i i
19

(B.8)

!

Again, fix the randomness with respect to a1 , . . . , am , y1 , . . . , ym , and remember that we have
conditioned on the event that the three statements in Lemma B.4 hold. Then with respect to the
ãi ’s, the quantity on the right in (B.8) is a centered Gaussian random variable with variance
σ2 =

m
CkHk2
1 X 2
2
2
Hx
k
y
ha
,
x
i
kP
≤
.
⊥
∗ 2
i
∗
i
x∗
m2
m
i=1

Therefore (hPx⊥
Σ̂Px∗ , Hi)X is a process indexed by X which has subgaussian increments with
∗
respect to the operator norm. We use an analogue of Theorem B.1 (see Theorem 3.2 in [13]) to
obtain a probability 1 − δ/4 event over which
!
p
γ2 (K, k·k2 ) + log(1/δ)
√
Σ̂Px∗ , Hi ≤ C
sup hPx⊥
.
(B.9)
∗
m
X∈K
Combining the bounds (B.6), (B.9), and (B.7) gives us the statement we want.
Lemma B.4. Let a1 , . . . , am be independent standard Gaussians, and suppose that Assumption
(Af,g ) holds. Then for any δ > 0, so long as m ≥ C/δ, the following three statements hold
simultaneously with probability at least 1 − δ/4.
1.

m
X

f (hai , x∗ i)2 ≤ Cm.

m
X

yi2 f (hai , x∗ i)2 ≤ Cm.

i=1

2.

i=1

3. max f (hai , x∗ i) ≤ C log m.
1≤i≤m

Proof. Exactly the same as in Lemma 5.3.
Proof of Theorem 2.5. We repeat the argument of Theorem 2.2, but replace the Hölder’s inequality
bound of hΣ̂ − Σ, X− x∗ xT∗ i therein with the uniform deviation bound supplied by Lemma B.3.

20

