Generative Principal Component Analysis
Authors: Zhaoqiang Liu
Jiulong Liu
Subhroshekhar Ghosh
Jun Han
Jonathan Scarlett
Venue: ICLR 2022 Poster (2022)
Keywords: Principal component analysis
generative models
sparse principal component analysis
projected power methods
optimal statistical rates

Abstract: In this paper, we study the problem of principal component analysis with generative modeling assumptions, adopting a general model for the observed matrix that encompasses notable special cases, including spiked matrix recovery and phase retrieval. The key assumption is that the first principal eigenvector lies near the range of an $L$-Lipschitz continuous generative model with bounded $k$-dimensional inputs. We propose a quadratic estimator, and show that it enjoys a statistical rate of order $\sqrt{\frac{k\log L}{m}}$, where $m$ is the number of samples. Moreover, we provide a variant of the classic power method, which projects the calculated data onto the range of the generative model during each iteration. We show that under suitable conditions, this method converges exponentially fast to a point achieving the above-mentioned statistical rate. This rate is conjectured in~\citep{aubin2019spiked,cocola2020nonasymptotic} to be the best possible even when we only restrict to the special case of spiked matrix models. We perform experiments on various image datasets for spiked matrix and phase retrieval models, and illustrate performance gains of our method to the classic power method and the truncated power method devised for sparse principal component analysis.

Published as a conference paper at ICLR 2022
GENERATIVE PRINCIPAL COMPONENT ANALYSIS
Zhaoqiang Liu
Jiulong Liu
National University of Singapore dcslizha@nus. edu.. sg
Chinese Academy of Sciences
biulongliudlses cc ac.
Subhroshekhar Ghosh
Jun Han
National University of Singapore
PCG, Tencent
reggr 1 com
junhanjh@teenenttcco
Jonathan Scarlett
National University of Singapore scarlett&comp. nus edu. sq
ABSTRACT
In this paper, we study the problem of principal component analysis with genera- tive modeling assumptions, adopting a general model for the observed matrix that encompasses notable special cases, including spiked matrix recovery and phase retrieval. The key assumption that the first principal eigenvector lies near the range of an L-Lipschitz continuous generative model with bounded k- k-dimensional inputs. We propose quadratic estimator, and show that it enjoys statistical rate
of order V &log where m is the number of samples. Moreover, we provide a variant of the classic power method, which projects the calculated data onto the range of the generative model during each iteration. We show that under suit- able conditions, this method converges exponentially fast to point achieving the above-mentioned statistical rate. This rate is conjectured in (Aubin et al. 2019 Cocola et al.) 2020) be the best possible even when we only restrict the spe- cial case of spiked matrix models. We perform experiments on various image datasets for spiked matrix and phase retrieval models, and illustrate performance gains of our method to the classic power method and the truncated power method devised for sparse principal component analysis.
INTRODUCTION
Principal component analysis (PCA) is one of the most popular techniques for data processing and dimensionalityy reduction (Jolliffe 1986), with an abundance of applications such as image recogni- tion (Hancock et al., 1996). gene expression data analysis (Alter et al. (2000), and clustering (Ding) & He 22004) Liu & Tan, 2019). PCA seeks to find the directions that capture maximal variances in vector-valued data. In more detail, letting X1, X2,..., X. be realizations of a random vector x E R" with population covariance matrix Σ E ROxn PCA aims to reconstruct the top principal eigenvectors of Σ. The first principal eigenvector can be computed as follows:
u1 arg max w T Ew wER"
s.t.
||w =
where the empirical covariance matrix is defined Σ = EE - cx c)T, with c == 1 Σm - x4. In addition, subsequent principal cigenvectors can be estimated by similar optimization problems subject to being orthogonal to the previous vectors.
PCA is consistent in the conventional setting where the dimension of the data is relatively small compared to the sample size m (Anderson, 1962). but leads to rather poor estimates in the high- dimensional setting where < In particular, it has been shown in various papers that the empiri- cal principal eigenvectors are no longer consistent estimates of their population counterparts (Nadler)
"Corresoondigg authors.

---

Published as a conference paper at ICLR 2022
2008 Johnstone & Lu 2009 Jung& & Marron 2009 Birnbaum al. 2013). In order to tackle the
curse of dimensionality, a natural approach is to impose certain structural constraints on the princi- pal cigenvectors. A common assumption is that the principal eigenvectors rise to the problem of sparse principal component analysis (SPCA) (Zou et al. (006). In partieular, for recovering the top principal eigenvector, the optimization problem of SPCA given by
sparse, and this gives
U1
arg max w' Ew WER"
s.t. | 122 = 1. |w/loo S 8,
where |/w/o- = Ki # 0}| denotes the number of non-zero entries of w, and E N represents the sparsity level. In addition to reducing the effective number of parameters, the sparsity assumption also enhances the interpretability (Zou et al. 2006).
Departing momentarily from the PCA problem, recent years have seen tremendous advances in deep generative models in a wide variety of real-world applications (Foster 2019). This has motivated new perspective of the related problem of compressed sensing (CS), in which the standard sparsity assumption is replaced by a generative modeling assumption. That is, the underlying signal is as- sumed to lie near the range of a (deep) generative model (Bora et al. 2017). The authors of (Bora et al. 2017) characterized the number of samples required to attain also presented numerical results on image datasets showing that compared to sparsity- based meth- ods, generative priors can lead to large reductions (e.g.. factor of 5 to 10) in the number of mea- surements needed to recover the signal up to a given accuracy. Additional numerical and theoretical results concerning inverse problems using generative models have been provided in (Van Veen al., 2018
accurate reconstruction, and
Dhar et al.,||2000 2018 Heckel & Hand [0199] Jalal ct al. 20200 Liu & Scarlett [2020a] Onngee et al.
Jalal
2020
Whang et al. 1020|Jalal et al. 2021 Nguyen et al. 2021), among others.
In this paper, following the developments in both PCA/SPCA and inverse problems with generative priors, we study the use of generative priors in principal component analysis (GPCA), which gives a generative counterpart of SPCA in (2), formulated as follows:
u arg max w Ew s.t. WERn
Range(G),
(3)
where G is a (pre-trained) generative model, which we assume has a range contained in the unit sphere of R² Similarly to SPCA, the motivation for this problem is to incorporate prior knowl- edge on the vector being recovered (or alternatively, a prior preference), and to permit meaningful recovery and theoretical bounds even in the high-dimensional regime < n.
1.1 RELATED WORK
In this subsection, summarize some relevant works, which can roughly be divided into (i) the SPCA problem, and (ii) signal recovery with generative models.
SPCA: It has been proved that the solution of the SPCA problem in attains the optimal statistical rate vss log n/m (Vu & Lei 2012). where m is the number of samples, is the ambient dimension, and s is the sparsity level of the first principal eigenvector. However, due to the combinatorial constraint, the computation of (2) is intractable. To address this computational issue, in recent years, an extensive body of practical approaches for estimating sparse principal eigenvectors have been proposed in the literature, including (d) Aspremont al., (2007; Vu al. 2013 Chang et al.]
2016 Moghaddam et al. 2006 0 A'Apreooont et al. 2008 Jolliffe f et al. 2003
Zou et al.) 2006 Shen
& Huang 2008 Journée Jooréeeer et al. 2010 Hein & Bühler 2010 Kuleshov
2013 Yuan & Zhang 2013
Asteris et al. 2011 Papailiopoulos et al. 2013), just to name few.
Notably, statistical guarantees for several approaches have been provided. The authors of Yuuan & Zhang, 2013) propose the truncated power method (TPower), which adds truncation operation to the power method to ensure the desired level of sparsity. It is shown that this approach attains the optimal statistical rate under appropriate initialization. Most approaches for SPCA only focus on estimating the first principal eigenvector, with a certain deflation method (Mackey 2008) being leveraged to reconstruct the rest. However, there are some exceptions; for instance, an iterative thresholding approach is proposed in (Ma] 2013). and is shown to attain a near-optimal statistical rate
'Similarly to (Liu et al. for convenience. Our results readily transfer to general (unnormalized) generative models by considering its normalized version. See Remark [T for a detailed discussion.
2020 202
we assume that the range of G is contained in the unit sphere
2

---

Published as a conference paper at ICLR 2022
when estimating multiple individual principal eigenvectors. In addition, the authors of (Cai al. 2013) propose a regression-tye -type method that gives an optimal principal subspace estimator. Both works (Mal 2013] Cai et al. 2013) rely on the assumption of a spiked covariance model to ensure good initial vector. To avoid the spiked covariance model assumption, the work (Wang et al. 2014) proposes two-stage procedure that attains the optimal subspace estimator in polynomial time.
Signal recovery with generative models:
Since the seminal work (Bora et al. 2017). 7. there has been
substantial volume of papers studying various inverse problems with generative priors. One of the problems more closely related to PCA is spectral initialization in phase retrieval, which amounts to solving an eigenvalue problem. Phase retrieval with generative priors has been studied in (Hand)
let al. 2018 Hyder et al.
2019; Jagatap & Hegde, 2019; Wei et al. 2019; (hhamshad & Ahmedd 2020 Aubin et al.] 2020, Liu et al.) 202Tb). In partieular, the work (Hand et al. (018)) models the underlying signal as being in the range of a fully-connected ReLU neural network with no off- sets, and all the weight matrices of the ReLU neural network are assumed to have i.i.d. zero-mean Gaussian entries. In addition, the neural network needs to be sufficiently expansive in the sense that n, 2 [ log n1;-)) where n; is the width of the i-th layer. Under these assumptions, the authors establish favorable global optimization landscapes for the corresponding objective, and de- rive a near-optimal sample complexity upper bound. They minimize the objective function directly over the latent space in R using gradient descent, which may suffer from local minima in general optimization landscapes (Hyder et al. 2019 Shah & Hegde (018)).
In (Aubin al.) 2020), the assumptions on the neural network are similar to those in (Hand al. 2018), relaxing to general activation functions (beyond ReLU) and n; 2 5((n=-1). The authors focus on the high dimensional regime where n, m, k oo with the ratio m/n being fixed, and assume that the input vector in R* is drawn from a separable distribution. They derive sharp asymptotics for the optimal performance and for the associated approximate message passing (AMP) algorithm. Both works (Hand et al., 2018; AAubin et al.) 2020) focus on noiseless phase retrieval. When only making the much milder assumption that the generative model is Lipschitz continuous, with no assumption on expansiveness, Gaussianity, and offsets, spectral initialization step (similar to that of sparse phase retrieval) is typically required in order to accurately reconstruct the signal (Netrapalli et al. 2015 Candès et al. 2015). The authors of (Liu et al. (021bb propose an optimization problem similar to (3) for the spectral initialization for phase retrieval with generative models. It was left open in (Liu al. 2021b) how to solve (or approximate sufficiently accurately) the optimization problem in practice.
Understanding the eigenvalues of spiked random matrix models has been a central problem of ran- dom matrix theory, and spiked matrices have been widely used in the statistical analysis of SPCA. Recently, theoretical guarantees concerning spiked matrix models with generative priors have been provided in (Aubin et al. 2019; Cocola et al. 2020). In particular, in (Aubin et al., 2019), the as- sumptions are similar those in (Aubin et al. 2020), except that the neural network is assumed to have exactly one hidden layer. The Bayes- performance is analyzed, and it is shown that the AMP algorithm can attain this optimal performance. In addition, the authors of (Aubin et al.) 2019) propose the linearized approximate message passing (LAMP) algorithm, which is a spectral algo- rithm specifically designed for single-layer feedforward neural networks with no bias terms. The authors show its superiority to classical PCA via numerical results on the Tashion-MNIS" dataset. In (Cocola et al. 2220)), the same assumptions are made as those in (Hand et al., 2018) on the neural network, and the authors demonstrate the benign global geometry for a nonlinear least squares ob- jective. Similarly to (Hand et al., 2018), the objective is minimized over IR* using a gradient descent algorithm, which can get stuck in local minima for general global geometries.
1.2 CONTRIBUTIONS
The main contributions of this paper are as follows:
We study eigenvalue problems with generative priors (including GPCA), and characterize the statistical rate of quadratic estimator similar to under suitable assumptions.
We propose a variant of the classic power method, which uses an additional projection operation to ensure that the output of each iteration lies in the range of a generative model. We refer to our method as projected power method (PPower). We further show that under appropriate conditions (most notably, assuming exact projections possible), PPower
3

---

Published as a conference paper at ICLR 2022
obtains solution achieving statistical rate that is conjectured to be optimal in (Aubin ct al. |
Cocola et al. 2020) for spiked matrix models.
For the spiked matrix and phase retrieval models, we perform numerical experiments on image datasets, and demonstrate that when the number of samples is relatively small com- pared to the ambient dimension, PPower leads significantly better performance compared to the classic power method and TPower.
Compared to the ahove-mentioned works that use generative models, we make no assumption on expansiveness, Gaussianity, and offsets for the generative model, and we consider a data model that simultaneously encompasses both spiked matrix and phase retrieval models, among others.
1.3 NOTATION
We use upper and lower case boldface letters denote matrices and vectors respectively. We write [N] -1 (1, ... .N} for positive integer N, and we use Iy to denote the identity matrix in NxN. generarive model a function
D + R", with latent dimension k, ambient dimension n, and input domain D _ RR, We focus on the setting where k < n. For set S S R and generative
model G R + IR", we write G(S) = {G(z) : z E 5). We use |X 2- 2 to denote the spectral
norm of a matrix X. We define the bg ball (r) = (z E R& I S r for y [0, +oo].
5n-1 = {x Th ||x||2 1} represents the unit sphere in R The symbols C, C', C" are
absolute constants whose values may differ from line to line.
2 PROBLEM SETUP
In this section, we formally introduce the problem, and overview some important assumptions that we adopt. Except where stated otherwise, we will focus the following setting:
We have matrix V E g2xx satisfying
V E,
where E is a perturbation matrix, and V is assumed be positive semidefinite (PSD). For PCA and its constrained variants, V and V can be thought of as the empirical and population covariance matrices, respectively.
We have an I--Lipschitz continuous generative model G B (r) + RR.. For convenience, similarly to that in (Liu et al. 2020), assume that Rango C Sn-1
Remark 1. For general (unnormalized) L-Lipschitz continuous generative model G, can instead consider a corresponding normalized generative model G D - Sn-1 as in Liu et al. 2021b), where DD := {z E (h(r) [[G(z)]l2 > Rminn for some Rmin > 0, and
G(z)
TG Then, the Lipschitz constant of G becomes L/ EmRnn For d-layer neural
Ciz)
network, we typically have L, = n @(d) (Bora et al. 2017). Thus, we can set Rman to be as
small as 1/n without changing the scaling laws, which makes the dependence on Rmin very mild.
We aim to solve the following eigenvalue problem with generative prior
V = max w Vw s.t. w E Range(G)..
(5)
WER"
Note that since Range(G) (G) C 1n1 do not need to impose the constraint ||w|]2 = 1. Since V is not restricted to being an empirical covariance matrix, (5) is more general than GPCA in B3. However,
slightly abuse terminology and also refer to (5) as GPCA.
To approximately solve (5). we use projected power method (PPower), which is described by the following iterative procedure
w (++1) Pa (Vw,
(6)
"To find the top r rather than top one principal eigenvectors that are in the range of a generative model,
may follow the common approach to use the iterative deflation method for PCA/SPCA: Subsequent prin- cipal eigenvectors are derived by recursively removing the contribution of the principal eigenvectors that calculated already under the generative model constraint. See for example (Mackey) 2008).
In similar iterative procedures, some works have proposed to replace V by PL, for some p E R to improve convergence, e.g., see Deshpande al. 2014).
4

---

Published as a conference paper at ICLR 2022
Algorithm 1 A projected power method for GPCA (PPower)
Input: V, number of iterations T. pre- pre-trained generative model G. initial vector w-())
Procedure: Iterate (1+ = Pa ( Vw(()) for t E {0, 1, T 1}. and return w-(T)
where P-(-) is the projection function onto G (r)) and the initialization vector (0) may be chosen either manually or randomly, e-g., uniform over S Often the initialization vector w()) plays an important role and we may need careful design for it. For example, for phase retrieval with generative models, as mentioned in (Liu et al. 2021b] Section V), we may choose the column corresponding to the largest diagonal entry of V as the starting point. See also (Yuan & Zhang 2013), Section 3) for a discussion on the initialization strategy for TPower devised for SPCA. We present the algorithm corresponding to O in Algorithm I]
Remark 2. To tackle generalized eigenvalue problems encountered in some specific appli- cations, there are variants of the projected power method, which combine a certain power iteration with additional operations to ensure sparsity or enforce other constraints. These ap- plications include but not limited to sparse PCA (Journée et al.) [010 Yuan & Zhang [01 3), phase synchronization (Boumal [016] Liu et al.) (017)) the hidden clique problem (Desh- pande & Montanari (015), the joint alignment problem (Chen & Candēs) 2018), and cone- constrained PCA (Deshpande et al. 2014 Yi Neykov [2020) For example, under the simple spiked Wigner model (Perry et al.) 2018) for the observed data matrix V with the underlying signal being assumed to lie in a convex cone, the authors of (Deshpande et al.) (2014) show that cone-conse constraind PCA can be computed efficiently via a generalized projected power method. In general, the range of a sppschiz--ontinmun
generative model is non-convex and not a cone. In addition, we consider matrix model that is more general than the spiked Wigner model.
Although it is not needed for our main results, we first state a lemma (proved in Appendix (A] that establishes monotonicity property with minimal assumptions, only requiring that V is PST) also Proposition 3 of Yuan & Zhang (2013) for an analog in sparse PCA. By comparison, our main results in Section 4 will make more assumptions, but will also provide stronger guarantees. Note that the PSD assumption holds, for example, when E = O, or when V is sample covariance matrix.
Lemma 1. For any x E R", let Q(x)= = xT Vx. Then, if is PSD, the sequence (1x0
w(') in 6 is monotonically non- con-decreasing..
3 SPECIALIZED DATA MODELS AND EXAMPLES
In this section, we make more specific assumptions on V + E, starting with the following.
Assumption 1 (Assumption on V). Assume that V is PSD with eigenvalues X1 > X2 2 X, 2
2
We use (a unit vector) to represent the eigenvector V that corresponds to A1-
In the following, it is useful to think of x is being close to the range of the generative model G. In the special case of (3). letting m be the number of samples, it is natural to derive that the upper bound of [|Ela--2 grows linearly in (n/m)² for some positive constant b such as 1 1 (with high probability; see, e.g., (Vershynin 2010, Corollary 5.35)). In the following, we consider general scenarios with V depending on m samples (see below for specific examples). Similarly to (Yuan & Zhang 2013), we may consider a restricted version of |Eil leading to the following.
Assumption 2 (Assumption E). Let S1, S2 be two (arbitrary) finite sets in IR satisfying [[og[[S]| - [Sal)). Then, we have for all 8 E S₁ and $2 E S2 that
log( 111. (S2l)
|s Espl S CV-
||s lla ||s2||2,
where C' is an absolute constant. In addition, we have |E] El|2-22 = ((n/m)
[w x| 2. We will implicitly assume that the projection step can be performed accurately, e.g., (Deshpande et al, 20144) Shah & Hegde 2018 Peng et al.
*That is, for any x E RR, Pe(x) := arg mill
2020 though in practice approximate methods might be needed, e.g., via gradient descent (Shah & Hegde
2018 or GAN-based projection methods (Raj et al. [2019).
For the spectral norm of E, one often expects an even tighter bound Ol O(Vn/m), but we use O(n/m) simplify the analysis of our examples. Moreover, least under the typical scaling where T. is polynomial
5

---

Published as a conference paper at ICLR 2022
The following examples show that when the number of measurements is sufficiently large, the data matrices corresponding to certain spiked matrix and phase retrieval models satisfy the above as- sumptions with high probability. Short proofs are given in Appendix [ for completeness.
Example (Spiked covariance model). the spiked covariance model (Johnstone & Lu 2009 Deshpande & Montanari 2016), the observed vectors X1, X2. Xm I of the form
X; Σ V Zi:
q=1
where .1...... Sy E R" are orthonormal vectors that we want to estimate, while (N and ugg ~ (0, 1) are independent and identically distributed. addition, $I,...,Br Br are positive constants that dictate the signal- signal-to-noise to-soise ratio (SNR). To simplify the exposition, we focus on the rank-one case and drop the subscript q E [r]. Let
V
[xxx] -In)
(9)
and V V Bsss" TT
Then, V satisfies Assumption 7 with = X2
and x s. In addition, letting E = V V, the Bernstein-type inequality (Vershynnn 2010 Proposition 5.10) for the sum of sub-exponential random variables yields that for any finite sets $1. S2 C T when m = 22 [og[[S]] (S2S))-SS2))... with probability 1 -
E satisfies 7
in Assumption 2 Moreover, standard concentration arguments give | = O(n/m) with prob-
ability - -
Remark 3. We can also consider the simpler spiked Wigner model Perry al. 2018 Chung & Lee 2019) where V = Bsss + H. with the signal s being a unit vector, 3 > 0 being an SNR
parameter, and H R being symmetric matrix with entries drawn i...d. (up to symmetry) from N(0. )- In this case, when m = n is sufficiently large, with high probability, V := E[V = βss" and E = V -V similarly satisfy Assumptions and respectively.
Example 2 (Phase retrieval). Let A E 1Rmx= be matrix having i..d. N(0 1) entries, and let a. be the i-th row of A. For some unit vector suppose that the observed vector is y |As], where the absolute value is applied element-wit wisee We construct the weighted empirical covariance matrix as follows (Zhang al. [2077: Liu et al. 2021b):
(ua ((ssiea) - 7Im),
(10)
(1<10 where u. 1> 1 are positive constants, and for g N(O, 1), 7 = B[lg [ <ull Let V
V 3ssT, where == EE [[g]] 1 ((<(s))<<)) Then, V satisfies Assumption I with Å1 Xn O, and x s. addition, letting
8>0 X₂
V, we have similarly to
Example that E satisfies Assumption with high probability.
MAIN RESULTS
The following theorem concerns globally optimal solutions of (5). The proof is given in Appendix Theorem 1. Let V V + E with Assumptions [ aand 2 satisfied by V and E respectively, and let XG (x) arg minnwe ||w x||2- Suppose that & is a globally optimal solution
Then, for any 8 E (0, 1), we have
0
log Fr
(V/
ön/m
+ Gn)llx xall2 (11)
VV xxx
||F
+0
A
V A1 X2
N -
where En O(V O00//oo X
log is
in (Bora et al. 2017). the upper bound for |E||2-2 can he casily relaxed to ((n/m)²) for any positive constant D without atfecting the scaling of our derived statistical rate.
To avoid non-essential complications, 33 is typically assumed to be known (Johnstone & Lu 2009).
Without loss of generality, we assume that is unit vector. For a general signal we may instead focus on estimating s/|||||2- and simply use 1 5 31 approximate ||s|||-

---

Published as a conference paper at ICLR 2022
We have stated this result upper bound on llvvt xx which intuitively measures the distance between the ID subspaces spanned by v and x. Note, however, that for any two unit vectors W1, W2 with w/ W. O, the distances ||w, W2ll2 and ||w, waw? l|r are equivalent up to constant factors, whereas if w/ W2 S 0, then a similar statement holds for W1 + w2ll2. See Appendix
C for the precise statements.
In Theerrm I the final term quantifies the effect of representation error. When there is no such error (i.e., X E Ra)) under the scaling λ1 X2 = ( L = =n 220)), and = O(1nn) Theorem
simplifies to V| - xx" || = OlV log L This provides a natural counterpart to the statistical rate of order
log for SPCA mentioned in Section
1.1
Before providing our main theorem for PPower described in 66. we present the following important lemma, whose proof is presented in Appendix E To simplify the statement of the lemma, we fix d be (1/nn,, though a more general form analogous to Theorem D also possible.
7 and being satisfied by V and E respectively, and further assume that x E Rango(G). Let 7. = X2/ A1 with \₁ = (1). Then, for all E Range(G) satisfying s" x+> >
Lemma 2. Let V = V E with Assumptions
we have
25 s
x
1
C <log(LLr)
[Poo(Vs) - x112 S
(12)
S
m
where C is an absolute constant.
Remark 4. The assumption s > 0 will be particularty satisfied when the range of G only con- tains nonnegative vectors. As mentioned in various works studying nonnegative SPCA ZZas & Shashua 2007: Sigg & Buhmmann 2008: Asteris et al., 2014), for several practical fields such as economics, bioinformatics. and computer vision, it is natural to assume that the underlying signal has no negative entries. More generally, the assumption s' & > can be removed if we additionally have that & is also contained in the range of G. For this case, when sT < O, can instead derive an upper bound for |s + x|22.
Based on Lemma 2 we have the following theorem, whose proof is given in Appendix
Theorem 2. Suppose that the assumptions on the data model V V + E are the same as those in Lemma and assume that there exists to E N such that x (ttt) = 25++v with 25 S 1-T, where 7 >2/A1 E [0. 1). and v, T are both positive and scale as (1). Let Nu
24 < 1,
x w't) 25+v
and addition, suppose that m 2 Cv., log(nTr) with Cu.z > 0 being large enough. Then, we have after Au = O (log ( (kogg(n))) iterations of PPower (beyond tq) that
C
k Alog(nLr)
[w(() - -x112
(13)
(1 MU)D
m
i.e., this equation holds for all 1 To == to + Do. Moreover, if = 0 then An S 1, whereas if 7 = ((1). have exponentially fast convergence via the following contraction property: There exists a constant & E (0, 1) such that for E [to, To), it holds that
[[((++1) - x||2 < (1 - [[][[(())) -
8|12.
(14)
Regarding the assumption x" (to) > 25 + v, we note that when to O, this condition can be viewed as having a good initialization. For both Examples [ and we have 7 0. Thus, for the spiked covariance and phase retrieval models corresponding to these examples, the assumption x (to 2 25 + reduces to x ((to) 2 v for a sufficiently small positive constant v, which results in mild assumption. Such assumption is also required for the projected power method devised for cone-constrained PCA under the simple spiked Wigner model, with the underlying signal being assumed lie in a convex cone; see (Deshpande et al. 2014 Theorem 3). Despite using a similar assumption on the initialization, our proof techniques are significantly different from Deshpande al. 2014); see Appendix G for discussion.
When L is polynomial in n. Theorem 2 reveals that we have established conditions under which
PPower in (6) converges exponentially fast to point achieving the statistical rate of order log L
7

---

Published as a conference paper at ICLR 2022
Based on the minimax rates for SPCA (Vu & Lei 2012 Birnbaum al., 2013) and the information-
theoretic lower bounds for CS with generative models (Liu & Scarlett 2020b Kamath et al.
2020),
the optimal rate for GPCA is naturally conjectured to be of the same order
llog We highlight
that Theorem 2 partially addresses the campputtiooall-oostttiiiiiiiii gap (e.g.. see (Wang et al. 2016
Hand et al. 2018 Aubin et al. 2019) Cocola et al. 22200) for spiked matrix recovery and phase retrieval under a generative prior, though closing it completely would require efficiently finding
good initialization and addressing the assumption of exact projections.
Perhaps the main caveat to Theorem is that it assumes the projection step can be performed exactly. However, this is a standard assumption in analyses of projected gradient methods, e.g., see (Shah & Hegde 2018), and both gradient-based projection and GAN-based projection have been shown to be highly effective in practice (Shah & Hegde 2018
Raj et al. 2019).
EXPERIMENTS
In this section, we experimentally study the performance of Algorithm (PPower). We note that these experiments intended as a simple proof of concept rather than seeking to be comprehen- sive, as our contributions are primarily theoretical. We compare with the truncated power method (TPower) devised for SPCA proposed in (Yuan & Zhang, 2013 Algorithm 1) and the vanilla power method (Power) that performs the iterative procedure w w (Vw(+))/1 Vw.(0/2. For fair comparison, for PPower, TPower, and Power, we use the same initial vector. Specifically, as mentioned in (Liu et al., 2021b, Section V), we choose the initialization vector w()) as the column of V that corresponds to its largest diagonal entry. For all three algorithms, the total number of iter- ations T' is set to be 30. To compare the performance across algorithms, we use the scale-invariant (x.w
Cosine Similarity metric defined as Cossim (x, (1)) ==
wa where x is the ground-truth signal to estimate, and (T) denotes the output vector of the algorithm.
The experiments are performed on the MNIST (LeCun al. 1998). Fashion-MNISS (iiao al. 2017) and CelebA (Liu et al., 2015) datasets, with the numerical results for the Fashion-MNIST and CelebA datasets being presented in Appendix H and The MNIST dataset consists of 60, 000 images of handwritten digits. The size of each image is 28 x 28, and thus = 784. To reduce the impact of local minima, we perform 10 random restarts, and choose the best among these. The cosine similarity is averaged over the test images, and also over these 10 random restarts. The generative model G is set be a pre-trained variational autoencoder (VAE) model with latent dimension i: = 20. We use the VAE model trained by the authors of (Bora et al.) 2017) directly, for which the encoder and decoder are both fully connected neural networks with two hidden layers, with the architecture being 20- 500 500- 784. The VAE is trained by the Adam optimizer with mini- batch size of 100 and a learning rate of 0.001. The projection step (G(.) is solved by the Adam optimizer with learning rate of 0.03 and 200 steps. In each iteration of TPower, the calculated entries are truncated to zero except for the largest entries, where E is a tuning parameter. Since for TPower, q is usually selected as an integer larger than the true sparsity level, and since it is unlikely that the image of the MNIST dataset can be well approximated by a k-sparse vector with 20, we choose a relatively large q, namely g = 150. Similarly (Bora et al. (017)) and other related works, we only report the results on test set that is unseen by the tre-trained VAE model, ie., the training of G' and the PPower computations do not use common data
1. Spiked covariance model (Example D: The numerical results are shown in Figures | and We observe from Figure that Power and TPower attain poor reconstructions, and the generative prior based method PPower attains significantly better reconstructions. To il- lustrate the effect of the sample size m, we fix the SNR parameter 3 1 and vary m in (100, 200, 300, 400, 500). In addition, to illustrate the effect of the SNR parameter B, we fix m 300, and vary in {0.6, 0.7, 0.8, 0.9, 1, 3, 4). From Figure ? we observe that for these settings of m and 3, PPowes always leads to much higher cosine similarity compared to Power and TPower, which is natural given the more precise modeling assumptions used.
$ All experiments are run using Python 3.6 and Tensorflow 1.5.0. with a NVIDIA GeForce GTX 1080 Ti 11GB GPU. The corresponding code is available at https: //gi wtt.. thub. com /uzgC9/ Generat vePCA
8

---

Published as a conference paper at ICLR 2022
7
2
4
4
7
7
2
4
9
S
9
Weosr Thwes Tonsr
2
1
6
4
9
7
2
6
1
9
1
S
(a) 3 1 and m 200
(b) B - 2 and m 100
Figure 1: Examples of reconstructed images of the MNIST dataset for the spiked covariance model.
0.8
0.6
Casine Simlanty
0.6
0.6
Thwe PPower
Wowee
9.4
PPower
0.4
PRower
0.2
0.2
0.2
0.0
0.0
0.0
100
150
200
250
300
350
400
450
500
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.5
200
400
600
800 1000 1200 1400 1600
(a) Fixing 3 and varying (b) Fixing
300 and varying 3
(c) Anallo of (a) for phase ret.
Quantitative comparisons of the performance of Power, TPower and PPower cording to the Cosine Similarity for the MNIST dataset, under both the spiked covariance model (Left/Middle) and phase retrieval model (Right).
Figure 2:
2. Phase retrieval (Example 2): The results are shown in Figure 2 (Right) and Figure 3 Again, we can observe that PPower significantly outperforms Power and TPower. In particular, for sparse phase retrieval, when performing experiments on image datasets, even for the noiseless setting, solving eigenvalue problem similar (5) can typically only serve initialization step, with a subsequent iterative algorithm being required to refine the initial guess. In view of this, it is notable that for phase retrieval with generative priors, PPower return meaningful reconstructed images for m 200, which is small compared to n 784.
spectral
6 CONCLUSION
We have proposed quadratic estimator for eigenvalue problems with generative models, and we showed that this estimator attains statistical rate of order V Log We provided projected power method efficiently solve (modulo the complexity of the projection step) the corresponding opti- mization problem, and showed that our method converges exponentially fast to point achieving
statistical rate of order
* log L under suitable conditions.
Acknowledgment.. J.S. was supported by the Singapore National Research Foundation (NRF) under grant 2-25520000-74--81 and S.G. was supported in part by the MOE grants R-146-000-2500 000--00---,,,,,, R- R-146-000-312-114 14, and
7
2
4
4
7
2
O
4
4
9
S
9
Pawer
RINE
Hower Theae
3
Q
4
1
4
9
7
2
7
2
1
6
4
1
4
4
4
9
(a)
200
(b)
400
Figure 3: Examples of reconstructed images of the MNIST dataset for phase retrieval.

---

Published as a conference paper at ICLR 2022
REFERENCES
Orly Alter. Patrick O Brown, and David Botstein. Singular value decomposition for genome-wide expression data processing and modeling. PNAS, 97000:10101110106, 2000.
Theodore Wilhur Anderson. An introduction to multivariate statistical analysis. Wiley New York, 1962.
Megasthenis Asteris, Dimitris Papailiopoulos, and George Karystinos. Sparse principal compo- nent of a rank-deficient matrix. In Int. Symp. Inf. Theory (ISIT), pp. 673-677. IEFE, 2011.
Megasthenis Asteris, Dimitris Papailiopoulos, and Alexandros Dimakis. Nonnegative sparse PCA with provable guarantees. In Int. Conf. Mach. Learn. (ICML), pp. 1728-1736. PMLR, 2014.
Benjamin Aubin, Bruno Loureiro, Antoine Maillard, et al. The spiked matrix model with generative priors. Conf. Neur. Inf. Proc. Sys. (NeurIPS), 32:8366-833 2019.
Benjamin Aubin, Bruno Loureiro, Antoine Baker, et al. Exact asymptotics for phase retrieval and compressed sensing with random generative priors. In Math. Sci. Mach. Learn. (MSML), pp. 55-73. PMLR, 2020.
Aharon Birnbaum, lain M Johnstone, Boaz Nadler, and Debashis Paul. Minimax bounds for sparse PCA with noisy high-dimensional data. Ann. Stat., 41(3): 2013.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using genera- tive models. In Int. Conf. Mach. Learn. (ICML), pp. 537-546, 2017.
Nicolas Boumal. Nonconvex phase synchronization. SIAM J. Optim., 26(4):2355-2377 2016.
T Tony Cai, Zongming Ma, and Yihong Wu. Sparse PCA: Optimal rates and adaptive estimation. Ann. Stat., (6)330077 10, 2013.
Emmanuel J Candès, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via Wirtinger flow: Theory and algorithms. IEEE Trans. Inf. Theory, 6185):1885-007,, 2015.
Xiaojun Chang, Feiping Nie, Yi Yang, et al. Convex sparse PCA for unsupervised feature learning. ACM T. Knowl. Discov. D., 11(1):1-16, 2016.
Yuxin Chen and Emmanuel J Candès. The projected power method: An efficient algorithm for joint alignment from pairwise differences. Comm. Pure Appl. Math., 1148)1164--1714 2018.
Hye Won Chung and Ji Oon Lee. Weak detection of signal in the spiked Wigner model. In Int. Conf.
Mach. Learn. (ICML), pp. 1233-1241. PMLR, 2019.
Jorio Cocola, Paul Hand, and Vlad Voroninski. Nonasymptotic guarantees for spiked matrix recov- ery with generative priors. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), volume 33, 2020.
Alexandre d' Aspremont, Laurent El Ghaoui, Michael Jordan, and Gert RG Lanckriet. A direct formulation for sparse PCA using semidefinite programming. SIAM Rev., 49(3) 448, 2007.
Alexandre d' Aspremont, Francis Bach, and Laurent El Ghaoui. Optimal solutions for sparse princi- pal component analysis. J. Mach. Learn. Res., 9(7), 2008
Yash Deshpande and Andrea Montanari. Finding hidden cliques of size vN/e in nearly linear time. Found. Comput. Math., 1564):1069-1128, 2015.
Yash Deshpande and Andrea Montanari. Sparse PCA via covariance thresholding. J. Mach. Learn. Res., 17(1):913-4955, 2016.
Yash Deshpande, Andrea Montanari, and Emile Richard. Cone-constrained principal component analysis. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), pp. 2717-2725, 2014.
Manik Dhar, Aditya Grover, and Stefano Ermon. Modeling sparse deviations for compressed sensing using generative models. In Inf. Conf. Mach. Learn. (ICML), pp. 1214-1223, PMLR, 2018.
10

---

Published as a conference paper at ICLR 2022
Chris Ding and Xiaofeng He. K-mmans clustering via principal component analysis. In Int. Conf. Mach. Learn. (ICML), pp. 2004.
David Foster. Generative Deep Learning: Teaching Machines to Paint, Write, Compose and Play. O'Reilly Media, Inc, USA, 2019.
Peter JB Hancock, A Mike Burton, and Vicki Bruce. Face processing: Human perception and principal components analysis. Mem. Cogn., 24(1):26 1996.
Paul Hand, Osear Leong, and Vladislav Voroninski. Phase retrieval under generative prior. In Conf. Neur: Inf. Proc. Sys. (NeurIPS), pp. 915.155441 9154-9164, 2018.
Reinhard Heckel and Paul Hand. Deep decoder: Concise image representations from untrained non-convolutional networks. In Int. Conf. Learn. Repr. (ICLR), 2019.
Matthias Hein and Thomas Bühler. An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA. Conf. Neur. Inf. Proc. Sys. (NeurIPS), pp- 847-855, 2010.
Rakib Hyder, Viraj Shah, Chinmay Hegde, and M Salman Asif. Alternating phase projected gradient descent with generative priors for solving compressive phase retrieval. In IEEE Int. Conf. Acoust. Sp. Sig. Proc. (ICASSP), pp. 7705-7709, 2019.
Gauri Jagatap and Chinmay Hegde. Algorithmic guarantees for inverse imaging with untrained network priors. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), volume 32, 2019.
Jalal, S Karmalkar, A Dimakis, and E Price. Instance-optimal compressed sensing via posterior sampling. In Int. Conf. Mach. Learn. (ICML), 2021.
Ajil Jalal, Liu Liu, Alexandros G Dimakis, and Constantine Caramanis. Robust compressed sensing using generative models. Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2020.
lain M Johnstone and Arthur Yu Lu. On consistency and sparsity for principal components analysis in high dimensions. J. Am. Stat. Assoc., 104(486):682 693226693660 2009.
Ian T. Jolliffe. Principal component analysis. Springer-Verlann Verlag, 1986.
Ian T Jolliffe, Nickolay T Trendafilov, and Mudassir Uddin. A modified principal component tech- nique based on the Lasso. J. Comput. Graph. Stat., 12(3)5531-547, 2003.
Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. J. Mach. Learn. Res., 11(2), 2010.
Sungkyu Jung and Stephen Marron. PCA consistency high dimension, low sample size context. Ann. Stat., 3716 2009.
Akshay Kamath, Sushrut Karmalkar, and Eric Price. On the power of compressed sensing with generative models. In Int. Conf. Mach. Learn. (ICML), pp. 5101-5109, 2020.
Volodymyr Kuleshov, Fast algorithms for sparse principal component analysis based on Rayleigh quotient iteration. In Int. Conf. Mach. Learn. (ICML), pp. 1418-1425. PMLR, 2013.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proc. IEEE, 86(11):2278-233 22222244, 1998.
Huikang Liu, Man-Chung Yue, and Anthony Man-Cho So. On the estimation performance and convergence rate of the generalized power method for phase synchronization. SIAM J. Optim., 27 (4):2426-2446,, 2017.
Zhaoqiang Liu and Jonathan Scarlett. The generalized Lasso with nonlinear observations and gen- erative priors. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), volume 33, 2020a.
Zhaoqiang Liu and Jonathan Scarlett. Information Information-theoretiee theoretic lower bounds for compressive sensing with generative models. IEFE J. Sel. Areas Inf. Theory, (1):2922303, 2020b.
11

---

Published as a conference paper at ICLR 2022
Zhaoqiang Liu and Vincent YF Tan. The informativeness of k-means for learning mixture models. IEEE Trans. Inf. Theory, (5(11))7460-7777 2019.
Zhaoqiang Liu, Selwyn Gomes, Avtansh Tiwari, and Jonathan Scarlett. Sample complexity bounds for 1-bit compressive sensing and binary stable embeddings with generative priors. In Int. Conf. Mach. Learn. (ICML), 2020.
Zhaoqiang Liu, Subhroshekhar Ghosh, Jun Han, and Jonathan Scarlett. Robust 1- bit compressive sensing with partial Gaussian circulant matrices and generative priors. https://arrivorrg2100...333 2021a.
Zhaoqiang Liu, Subhroshekhar Ghosh, and Jonathan Scarlett. Towards sample-optimal compressive phase retrieval with sparse and generative priors. Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2021b.
Ziwei Liu, Ping Luo. Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Int. Conf. Compur. Vis. (ICCV), pp. 3730-3736 2015.
Zongming Ma. Sparse principal component analysis and iterative thresholding. Ann. Stat., 41(2): 772-801, 2013.
Lester W Mackey, Deflation methods for sparse PCA. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), volume 21, pp. 1017-1024, 2008.
Baback Moghaddam, Yair Weiss, and Shai Avidan. Spectral bounds for sparse PCA: Exact and greedy algorithms. Conf. Neur. Inf. Proc. Sys. (NeurlPS), 18:915, 2006.
Boaz Nadler. Finite sample approximation results for principal component analysis: A matrix per- turbation approach. Ann. Stat., 36(6)27911-2817, 2008
Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi. Phase retrieval using alternating minimiza- tion. IEEE Trans. Sig. Proc., 63(18))4814 4826. 2015.
Thanh V Nguyen, Gauri Jagatap, and Chinmay Hegde. Provable compressed sensing with generative priors via Langevin dynamics. hmmp::/aarxi.orr//100..222 12643, 2021.
Gregory Ongie, Ajil Jalal, Christopher A Metzler, et al. Deep learning techniques for inverse prob- lems in imaging. JEEE J. Sel. Areas Inf. Theory, 1(1):39-56, 2020.
Dimitris Papailiopoulos, Alexandros Dimakis. and Stavros Korokythakis. Sparse PCA through low- rank approximations. In Int. Conf. Mach. Learn. (ICML), pp. 747-755, PMLR, 2013.
Pei Peng, Shirin Jalali, and Xin Yuan. Solving inverse problems via auto-encoders. JEEE J. Sel. Areas Inf. Theory, 1(1):312-323, 2020.
Amelia Perry, Alexander Wein, Afonso S Bandeira, and Ankur Moîtra. Optimality and sub- optimality of PCA I: Spiked random matrix models. Ann. Stat., 46(5):2416-2455 2018.
Ankit Raj, Yuqi Li, and Yoram Bresler. GAN-based projector for faster recovery with convergence guarantees in linear inverse problems. In IEEE/CVF Int. Conf. Comp. Vision (ICCV), 2019.
Viraj Shah and Chinmay Hegde. Solving linear inverse problems using GAN priors: An algorithm with provable guarantees. In Inl. Conf. Acoust. Sp. Sig. Proc. (ICASSP), pp. 4609-4613. IEBE, 2018.
Fahad Shamshad and Ali Ahmed. Compressed censing-based robust phase retrieval via deep gener- ative priors. IEEE Sens. J., 21(2):2286 2298, 2020.
Haipeng Shen and Jianhua Huang. Sparse principal component analysis via regularized low rank matrix approximation. J. Multivar: Anal., 9916): 2008.
Christian D Sigg and Joachim M Buhmann. Expectation-mxximizziion for sparse and non-negative PCA. In Int. Conf. Mach. Learn. (ICML), pp. 960-967, 2008.
Dave Van Veen, Ajil Jalal, Mahdi Soltanolkotabi, et al. Compressed sensing with deep image prior and learned regularization, https://azzivorr///886.... 064338 2018.
12

---

Published as a conference paper at ICLR 2022
Roman Vershynin.
Introduction to the non-asymplotic analysis of random matrices. http::/arxihoorgabb/111....// 2010.
Roman Vershynin. Hligh-iimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Vincent Vu and Jing Lei. Minimax rates of estimation for sparse PCA in high dimensions. Int. Conf. Artif. Intell. Stat. (AISTA7S), pp. 1278-1286. PMLR, 2012.
Vincent Q Vu, Juhee Cho, Jing Lei, and Karl Rohe. Fantope projection and selection: A near-optimal convex relaxation of sparse PCA. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), volume 26, 2013.
Tengyao Wang, Quentin Berthet, and Richard J Samworth. Statistical and computational trade-offs in estimation of sparse principal components. Ann. Stat., 44(5):1896-199) 2016.
Zhaoran Wang, Huanran Lu, and Han Liu. Tighten after relax: Minimax-optimal sparse PCA in polynomial time. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2014.
Xiaohan Wei, Zhuoran Yang, and Zhaoran Wang. On the statistical rate of nonlinear recovery in generative models with heavy-tailed data. Int. Conf. Mach. Learn. (ICML), pp. 6697-6706, 2019.
Jay Whang, Qi Lei, and Alexandros G Dimakis. Compressed sensing with invertible generative models and dependent noise. https://arrii.or//200.0000000 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: A novel image dataset for bench- marking machine learning algorithms. https://araivvor///0080777777 2017.
Yufei and Matey Neykov. Non-sparse PCA high dimensions via cone projected power iteration. https://artii.rgg/0000777758 2020.
Xiao-Tong Yuan and Tong Zhang. Truncated power method for sparse eigenvalue problems. J. Mach. Learn. Res., 14(4), 2013.
Ron Zass and Amnon Shashua. Nonnegative sparse PCA. In Conf. Neur Inf. Proc. Sys. (NeurIPS), pp. 1561-1568, 2007.
Huishuai Zhang, Yi Zhou, Yingbin Liang, and Yuejie Chi. A nonconvex approach phase retrieval: Reshaped Wirtinger flow and incremental algorithms. J. Mach. Learn. Res., 18, 2017.
Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. J. Comput. Graph. Stat., 15(2):265-286, 2006.
13

---

Published as a conference paper at ICLR 2022
APPENDIX (GENERATIVE PRINCIPAL COMPONENT ANALYSIS,
LIULIUUGHOOS//AANSCCAALTYY ICLR 2022)
A PROOF OF LEMMA
(NON-DECREASING [ PROPERTY OF Q)
Since ((+1)) Pa (Vwlo) and w(()) Range(G), have
Vw (1) w & Vw 11,,
(15)
and since |w (0) = 1, expanding the square gives
(ww(", w((tl)) 2 Q(w(1).
(16)
Then, obtain
Q(w((+1)) = (Vw(+t2) w((+1))
(17)
= =Q(w((+1) (()) + 2 (((w(++)) - -w())), m(()) + Q(w((())
(18)
2 2 ( (V(w(tt)) - w(()), m()) + ((w((())
(19)
2 Q(w(!))
(20)
where (8) follows by writing ((+1)) w(() (w(++1) w()) and expanding, 19) follows from
the assumption that V is PSD, and (20) follows from (16).
B PROOFS FOR SPIKED MATRIX AND PHASE RETRIEVAL EXAMPLES
Before proceeding, we present the following standard definitions.
Definition 1. A random variable is said to be sub-Gaussian if there exists a positive constant C such that (E [X < for all 2 1. The sub-Gaussin Gaussian norm of a sub-Gaussian random variable is defined as ||x1 = supp21 P 1122 (E [XP)))
Definition 2. random variable X is said to be sub-exponential if there exists a positive constant C such that (E [IXP)) < for all 2 1. The sub-exponential norm of X is defined as ||X [lv1 suPp21 P- (E|
The following lemma states that the product of two uub-Gaussian random variables is sub- exponential, regardless of the dependence between them.
Lemma 3. (Vershynin 2018 Lemma 2.7.7) Let and Y Sab-Gaussian random variables (not necessarily independent). Then XY is sub-exponential, and satisfies
|X||,, I ||X||v/]|||ll
(21)
The following lemma provides useful concentration inequality for the of independent sub- exponential random variables.
Lemma 4. (Vershynin 2010, Proposition 5.16) Let XI....,
be independent zero-mean sub- exponential random variables, and K max; [Xille,- Then for every = R and é 2 0, it holds that
axl"
2exp (-c.min
P
Σ axx
20)
K K|[al|>>)
(22)
K2I
where e is an absolute constant. In particular, with a ....., 11=,, we have
N N
< 2exp (-c min NNe2
K2 KK] )
2
(23)
14

---

Published as a conference paper at ICLR 2022
The widely-used notion of an e-net is introduced as follows.
Definition 3. Let (X, d) be metric space, and fix O. A subset S C X is said be an e-net of X if. for all X. there exists some s E S such that d(s, x) S The minimal cardinality of an c-net of X, if finite, is denoted C(X, t) and is called the covering number of X (at scale e).
The following lemma provides a useful upper bound for the covering number of the unit sphere. Lemma (Vershynin 2010 Lemma 5.2) The unil Euclidean sphere SN-1 equipped with the Euclidean metric satisfies for every >> 0 that
C(SN-1,e) c) - 1+ 2 N
2
(24)
The following lemma provides an upper bound for the spectral norm of symmetric matrix.
Lemma 6. (Vershynin 2010 Lemma 5.4) Let X be symmetric N x N matrix, and let C. be an e-nel of -I-IIp for some E 1/2). Then,
X 2-22 = sup rESH-1
[Xr, S (1 - 2e)- sup (Xr, r) rEC.
(25)
With the above auxiliary results in place, we provide the proofs of Assumption 2 holding for the two examples described in Section 3
B. SPIKED COVARIANCE MODEL (EXAMPLE
As per Assumption 2 fix two finite signal sets S₁ and Sg. For r 1, we have x; /Bu,s and a direct calculation gives E = = BässT Recall also that ||s||| = =1, u ~ NNO 1), and z, ~ (0,, I,). It follows that for any s E Si, we have that x /Bu,s"' + z,'ss is sub-Gaussian, with the sub-Gaussian norm being upper bounded by C(vB + 1i|ss ll2. Similarly, we have for any 82 S2 that ||s} x S C(VB + 1)[s2||12 Applying Lemma 3 we deduce that (sf x;) x;) is sub-exponential, with the sub-exponential norm being upper bounded by C²(BB 1) || ||a |22||22 In addition, from (9) and V = Bss", we have
i Es² = s V)82
(26)
1 m
(xx s1) (x{{2) ((sf52) + ((s"ss (s"
(27)
and we observe that [[(x3's) (x} 82)] (2f (s" (s" Then, from Lemma
we obtain
that for any & > satisfying m 21t)). the following holds with probability - 200 (recall that C' may vary from line to line):
I Σ ((xf's)) - (()fs))) + si) st)))
Vt
sss"s)s)sss (sF CCVB + 1)
(28)
where we note that the assumption m (tt) ensures that the first term is dominant in the minimum in (33. Taking a union bound over all s E S₁ and 82 E S2, and setting t = log[[S]] 1S2)). we obtain with probability -- e -A(lg](( (-1-a))) that (7) holds (with 3 being a fixed positive constant).
Next, we bound |r- Er| for fixed r E 5n-1, but this time consider L>> 0 (different from the above 1) satisfying/ = 2mm). In this case, we can follow the above analysis (with 8 and 82 both replaced by r), but the assumption
2(m) means that when applying Lemma 4 the second term in the minimum in (23) is now the dominant one. As a result, for any t satisTying t = Mmm), and any we have with probability 1 - e 2(()) that
r E S"
m
Erl
((xF))
(1+ r))))
(29)
m
C(VB+11) t
(30)
15

---

Published as a conference paper at ICLR 2022
From Lemma 5 there exists an (1/4)-net C of sm-1 satisfying log [c log 9. Taking union
bound over all E Cj. and setting & = Cn, we obtain with probability - e R(() that
sup rEC
| Er O
71
(31)
Then, from Lemma 6 we have
Er'Er| 0 (-))
E
2-+2 S sup
(32)
rEC;
B.2 PHASE RETRIEVAL (EXAMPLE 2
Let W 1 E U, (ISs)c)) and W Ass + TIa It is shown in (Liu et al.
2021b
Lemma 8) that
E W W.
(33)
which implies
E 3ss V.
(34)
Then, for any $1 S1 and S2 E S2, we have
of Esg = (
V)s = s[W W)82
(35)
1 Σ
ua sa s2) s2)1 [ccneu) (3(5" s:)==ss + ( (2)sss)))
(36)
Since each a; has i.dd NNO,1) 1) entries, we observe that (a 81 (a 82) <(<) is sub- exponential with the sub-exponential norm being upper bounded by Cullstl|a S2 l2- In addition, ss)(s"s)) + ( sz). Then, from Lemma we obtain that for any satisfying m (2()), with probability -000)
from (33, have (ay sı (a, (aaass))(eee (r<)<()))))))
Vi
(t)(("sssaasss))) ( - (3(sTs))($ (s)))) + +s( $ Culls1
m
Vm
(37)
Taking a union bound over all 8 E S₁ and 82 E S2, and setting / = log( (-((Sii-1S5) (S2)), we obtain that with probability 1 - -O(lo((S:)-188a)) (7) holds as desired (with u being a fixed positive constant).
In addition, similarly to 32 we have with probability - e eQ(n)) that E||2-12 = 0 (m))
C EQUIVALENCE OF DISTANCES
The following lemma gives useful equivalence between two distances.
Lemma 7. For any pair of unit vectors W1, W2 with w W2 2 0, we have
||
wall
|wiT Wow? 11: 2/|w1 well
(38)
Moreover, if w W2 < O, then the same holds with [|w, well2 replaced by [|w + well2-
Proof. When wi Wa 0, we have
(Wiwf ||w] w/" w2w = -r(((w]]] (w.w)" w2ww))
(39)
= 2 (1 (wi )2)
(40)
2 2 (1 w w2)
(41)
[w Wa
(42)
where 40
follows by expanding the product and writing tr(w wT w wT) = tr(w7 w, w (/]w =
(wf w) 1 and handling the other terms similarly, and (41) follows since w Wa E (0, 1). In
16

---

Published as a conference paper at ICLR 2022
addition, have
||iw? -2w = 2(1 (wf w2)
(43)
= 2 (1 w/ w2) (1 + w/ W2)
(44)
I 4 (1 w/ W2)
(45)
= 2/| Wy 12
(46)
which gives the desired inequality. The case wi W2 < 0 is handled similarly
D PROOF OF THEOREM I (GUARANTEE ON THE GLOBAL OPTIMUM)
Let the singular value decomposition (SVD) of V be
V ÜDU
(47)
where D = Diaag((),...... )m)). and U E R is an orthonormal matrix with the first column being x. For i 1, let the i-th column of U ú, Then, we have
VV X1 (x
X (u, v
(48)
S (x
A2
(u. v)²
(49)
= (x
da (xT))²)
(50)
where we use (x*v)² + Ei>1 (uf = 1 in 50
In addition, for any E R and any S1, S2 E IR" we have
s/ Asi
s As²
$1
52
S1 52
A
+
S2
S1
S2
2
2
81
+
81
82
81 S
81
A
(51)
2
2
2
2
T
81 + 82
81
82
81 82
81 + 82
A
+ 2
(52)
2
2
2
2
In particular, when A is symmetric, we obtain
o Asi
5 As
(s + 82) A(s - -52).
(53)
Let be a (D/L)-net of (r); from (Vershynin such net with
2010
Lemma 5.2), we know that there exists
4Lr 8
log
M
S klog
(54)
Since G is L-Lipschitz continuous, we have that G(M) is 8-net of Range(G) G(B)(r)). We write
= (v x) +
(55)
where Σ E G(M) satisfies - x1|2 S 6. Suppose that x 2 0; this not the case, we can use analogous steps to obtain an upper bound for x V/12 instead of ||x V/12. We have
Ni do
1 -
(56)
2
(di - 22) (1 v)
(57)
s (Ā1 Tz) (1 (1- (x x))
(58)
Å₁ - (Nr (x²))² + - (1 (1- vx-(x())))
(59)
17

---

Published as a conference paper at ICLR 2022
=x i (x"v)² + +82 (1 - (xx(v)))
(60)
s Vx'V8- VVVV
(61)
VxG + (8 + xx) VV(x -xo) - Vv
(62)
x Vxc XG + +2A11 xal22 VVVV
(63)
XV(V (V- E)xc + -2 X - x6l12 ("(V Ejv
(64)
S V'E Exe + +211/1x
xal2
(65)
v-x
T
V x
+
T
V
x 2
=x +2
E
2
E
xx
25 ||x
x 22
2
2
2
(66)
S ExE + 201|E|122>>
G
Exg + +21 xcl12
(67)
+G
XG
x
X6
T
x
X6
22
E
+2
E
+ +
2->2 + 2 ||
x 22
(68)
k log 8
4Dr
< $20V
|| x ||2 + 26 2-12 + 2/1 xGl12
(69)
m
4Lr A: log m
< 120
5
(1| - 2112 + |/ - | xall2) 2011E|12222 2
xol12 (70)
k klog 4hr
(δm)
Ön
S $20
/| x + +0
+0((2 +,]l/- xcll2),
(71)
m
m
where:
58
follow from ||x||2 || 1 and hence | 1;
60
follows since (Λ1,x) x) are eigenvalue-cigenveetoo pair for V with ||||| 1;
61
follows from 50
follows from
53
with V being symmetric and setting 8 x, 82 XG:
663
follows from X
Xg
and VV 2--2 = A1;
64
follows since V V E;
65
follows since v is globally optimal solution to 5 and Xg E Range(G);
666
follows from 52 with Sı and $2 = x:
667
follows from 55
along with || x||2 < 8 and V x||2 S 2;
688
follows from 52
follows from Assumption 2 (with Si S₂ being G(M) shifted by xg) and (54):
70
follows from the triangle inequality;
follows by substituting || x||2 < 8, along with the assumptions E 12 =
(n /m) m = (2(k log 4)), and E = =0(v
# log 4
m
From we have the following when 8 x 2 0:
o
log Ar. m
(v1
8n/m
(11 + en en)li xelle
V - x
+ 0
(V N1
+0
(72)
A1 X2
X
N1 - A2
18

---

Published as a conference paper at ICLR 2022
As mentioned earlier, if V X we obtain
O, we have the same upper bound as in (2) for +| Therefore,
VA
xxx
xxx11= 1|B =
1 2 (2(1- (xTV))
(73)
2 (211=xV) (1 (1+ xT
(74)
22min x||2, +
(75)
V A log 4r
11 / en
+0
6n/m
+0
en
|x xol12
(
(76)
\ A2
\1
d A2
where 73
follows from
40
75
follows from ||
+
x
= 2(1 + v) and 76 follows from
E
PROOF OF LEMMA 2 (AUXILIARY RESULT FOR PPOWER ANALYSIS)
By the assumption Range(G) C Sa for any x E R" and a > 0, we have
Pa(x) (a(ax).
(77)
which is seen by noting that when comparing ||x a l2 with ||x-bbi, b112 (in accordance with projection mapping to the closest point), long ||a|| ||b|l2 2. the comparison reduces to comparing (x, a) with (x, b), so is invariant to positive scaling of x.
Let 7j 1/A1 0 and å Pa(Vs), Then, have á Po(Vs) Po)() Since x Range(G), (G), we have
|s $12 S I1 x112.
(78)
This is equivalent
11 - x) + (X - -)113 < V7 - x112.
(79)
and expanding the square gives
x a|12 5 2 Vs x - x).
(80)
Note also that from Vx = λ1X, we obtain x = Vx, which we will use throughout the proof. For 0, let M be (net)- of (r); from Lemma there exists such a net with
4Lr log M S k log 6
(81)
By the L-Lipschitz continuity of G, we have that G(M) is a 8-net of Range(G) GrB)(r)). We write
(s sq) So,
= ($ 8) + s,
(82)
where š G(M) satisfies ||s š 8. and so E G(M) satisfies |ss soll2 8. Then, we have
Vr x, x) Vss - x), $ - x + Es, $ x)
(83)
which follows from V = V + E and x = r) Vx. In the following, we control the two terms in separately.
83
1. The term (s x), --))-)): We decompose = ox + ft and & = áx + 9ē, where ||t||2 [t|l 1 and t = fTx 0. Since ||s||| |||| 1, we have a² B2 a² + 3 = 1. addition, we have a = s x and å = ST Recall that in (47). we write the SVD of V V = ÜDÚT. Since t x 0,
write t t Σi>1 h,ū, In addition, since
19

---

Published as a conference paper at ICLR 2022
||||| 1, we have E h3 1. Hence, by the Sauchy-Schward inequality, we have
((t,, E - |
(84)
(85)
(86)
h2
(87)
1>1
d2
(88)
Therefore, we obtain
(x)s-x),88-
x) -)x8-x)
K(a 1)x + Vt, (a - 1)x + 36)1
(89)
= [(a ([a=-)((a-))) - 1) + (Vt,
(90)
$ (1 a) 6:) + 3//32
(91)
= (1 a)(1 a) + 5 v a² / 6²,
(92)
where 89 uses v) v & = 8, and (90) uses
| = 1 and (x, t) = 0.
2. The term En) - x): We have
Ens - x) (rTE(s so) + so) x)
(93)
En) - -u), x) + Esu, ($ - 5) + ($ x))
(94)
klog 4r
S 7| Bl12--2001 - 12 + 7 E 22 + O
||5 x
m
(95)
(v | Lr +0
0 (6 (2-2) +0
||$
x1|2.
(96)
m
where 955) follows from Assumption 2 and (8I. and 96) follows from ij = 1//1. along with the fact that we assumed λ₁ ([).
Note that ||x = ((1--sx)) = 2(1 -.) Hence, and using 80 83
92
and 96 we obtain
2(1 a) < (1 a1 - a) + a à²
klog Lr m
+ +0 +0
2/
(97)
Using 2(1 à) - 2(1 - (1 a) 2a a). vI az
av-avllt S 22 a), and
similarly VI- â²d s /2(1 â), we obtain from (97) that
Io & k log m
21 - a) s 25 25 2 a) 2 -
+
E (2)2)) (98)
Since ||s - x|12 2(1 â) and ||s - x113 = 2(1 a), this is equivalent to
27|ss x||2 + (1
k log Lr
m )) ||s x||2 + 0 E E|
a: |s x13 <
2--22
(99)
20

---

Published as a conference paper at ICLR 2022
This equation is of the form o.²² bz + (where 2 using a simple application of the quadratic formula we obtain
||s x||2 and = s 0), and
25 s
2
1
h log
Lr 8
|| x1|2
+ v 82/1111222-2
(100)
s
25 2
k klog(IIr)
0
(101)
Sx'
S
where we use the assumption |E||2_1 On and set d 1/n in (001).
F PROOF OF THEOREM 2 (MAIN THEOREM FOR PPOWER)
Suppose for the time being that 13) holds for at least one index 2 to (we will later verify that this the case), and let To 2 to be the smallest such index. Thus, we have
C
k klog(nIr)
w (Ta) x S
(102)
(1 po)
Y71
Note that according the theorem statement, 1 1- Mg is bounded away from zero. Using [ ||2 || and the assumption that m 2 Cz.r k log(nIr) with Cu.r > O being large enough, we 102) that [| x||2 is sufficiently small such that
deduce from
x (T)) 1-T
(103)
Next, using the assumption 25
+ < we write
29
1
25 (1 MO)
27 +
(104)
(1 (1- 11-1o)((1120
(1 1--Mo)(( 7) (1 Ho)b(1 -7) (1- po)v
Then, from Lemma 2 obtain
[[
x112
27
||w(fo) x112
C
klog(nLr)
(105)
x (Ta)
T (Ta)
m
27
C
Alog(nLr)
C
k blog(nLr)
$
(106)
7
(1 - HO)
m
m
C
k log(nLL)
(107)
pa)v
m
where (066) follows from 102
103 and (177) follows from 104). Thus, have transferred
102 from To to To + 1, and proceeding by induction, we obtain
k log(nIr)
|w(()) x1|2 - (1 Mo)v
(108)
for al f > To. Next, we consider [lu, To). Again using Lemma (with w((++)) Pa Pc(VV(()))) we have
C
klog(nTT) m
[[o+)) x1|2 S 140 [ool/weee (ta) x +
(109)
27 +
27 where we recall that μo =xT((o)) = 29 1, and note that the denominator in the second term of (I09) follows since x (f'(ffo) 25 + v. Supposing that to < To (otherwise, the above analysis for f 2 To alone is sufficient), we have that (3) is reversed at = to:
25
C
l log(nIr)
[ x122
(110)
Since leading coefficient
quadratic positive, must lie between the two associated
This yields b+ /b2+ from which the inequality Va + b < Va vb gives 100
21

---

Published as a conference paper at ICLR 2022
This means that we can upper bound the second term in (009) by e e. /oog(nbr) < (1- (1-No))|\m(b)
x||2, which gives
[| x||2
< |w (ta)
x/12.
(111)
Squaring both sides, expanding, and canceling the norms (which all equal one), we obtain
x (to+!)
x"vvv (to),
(112)
and by induction, we obtain that {x" (()) (e)(oo)T) Tb) is monotonically increasing.
Recall that we assume that Å (1), and that To to + Do is the smallest integer such that (13)
holds. To verify that To is finite and upper bound Ao. we consider the following three cases:
Ho = 0 (or equivalently. - A = 0): In this case, (009) gives To = to + 1 (or To = to. which
we already addressed above). Thus, have Ao S as stated in the theorem.
Ai = o(1) (or equivalently. 5 o(1) and d2 = o(1)): Since (x) )ee(oo.6) is monotoni-
cally increasing, for any positive integer A with 4 A < To. by applying Lemma multiple times, we obtain
Z (or (109)
1 A
C
llg((Lr)
|| -x112 S ((llw(()))) - -x112 +
(113)
1 Mu
27 +
C
klog(nLr)
S 16 (()) - -x112
(114)
1 14
25 + v
m
Then, if we choose Do E N such that
C
llgg(ITa)
16 s
(115)
2v
m
we obtain from (14b that
ww (to - x112 S Mo
Au [|w( (bo)
-x|12 +
1
C
k llg((LL))
(116)
1
Ho
27 +
1
C
k klog(nLr)
S 2p00 Ao
+
(117)
1- 410
27 +
m
Cho
1s log(nLr)
1
C
k llg(nLL)
(118)
v(1 Ho)
m
24
+
m
C
k klog(nLr)
(119)
MOJv
where 117 follows from (lw) x||2 S 2, (18) follows from 115) and
I- Ho
29 and 119 follows from μl 2540' which implies Ho 2944 (25++2))
2o(2++2)+v
25
=(25+v)
Observe that (119) coincides with (3)), and since
o(1), we obtain from 115) that
An = 0(1ogg [log(nLr]) )) as desired.
m
/40 (1) (or equivalently, 7 O1)) and X2 = (())): Recall that we only need to focus on
the case To > to. This means that (110) holds, implying that we can upper bound the second
term in 109 by (1-wa)e //ww(w)) x 1,, yielding
2544
|| (fo+t) 1) - x1|2 < noll Holl (to) xx|22 + (1 Ho)e
||w - x1|2
(120)
29 +
27 + (1-M0)e
/|w -01-xx1 -x112
(121)
27 +
= (1 - (l) 8/12:
(122)
IIn simpler notation, if 2++1 azz b,, then we get 2142 azzz- (1+a)b, then z413 S (d'zet(++ata")) and on, and then can apply +
a" a--1 I-e' for of
22

---

Published as a conference paper at ICLR 2022
2デ++ Mo no) (1). With the distance to x shrinking by constant factor in each iteration according to (122). and the initial distance |w x|2 being at most 2 due to the vectors having unit norm, we deduce that Ao = O log (Tlog(nLr)) iterations suffice to ensure that 133 holds for t = to + Ao.
where { = _ApK
m
G COMPARISON OF ANALYSIS TO DESHPANDE ET AL. (2014)
As mentioned in Section 4 our analysis is significantly different from that of Deshpande et al. (2014)
despite using a similar assumption on the initialization. We highlight the differences as follows:
1. Perhaps the most significant difference is that the proof of (Deshpande et al. 2014, Theorem 3) is highly dependent on the Moreau decomposition, which is only valid for a closed convex cone (see (Deshpande needs to be used at the beginning of the proof of (Deshpande et al. 2014] Theorem 3), such as Eqs. (18) and (19) in the supplementary material therein. We do not see way for the proof to proceed without the Moreau decomposition, and our Range(G) G) may be very different from a convex cone.
al., 2014 Definition 1.2)). In particular, the Moreau decomposition
2. We highlight that one key observation in our proof of Lemma (and thus Theorem 2 is that for a generative model G with Range(G) C S and any x E R" and a > 0, we have Pa(ax) (x) (Eq. (77)). This enables to derive the important equation & = Pa (VV)ss
Vs) s). We are not aware of a similar idea being used in the proof of (Deshpande et al. Theorem 3).
2014
3. In the PPower method in (Deshpande et al. 2014). the authors need to add pIn with p > 0 to the observed data matrix to improve the convergence. In particular, they mention in the paragraph before the statement of Theorem 3 that "the memory term gv is necessary for our proof technique to go through". In contrast, our proof of Theorem 2 does not require adding such terms, even when our data model is restricted to the spiked Wigner model considered in (Deshpande et al. 2014).
4. We consider matrix model that is significantly more general than the spiked Wigner model
studied in (Deshpande et al. 2014).
H NUMERICAL RESULTS FOR THE FASHION-MNIST DATASET
The Fashion-MNIST dataset consists of Zalando's article images with a training set of 60, 000 ex- amples and test set of 10, 000 examples. The size of each image in the Fashion-MNIST dataset is also 28 x 28, and thus n = 784.
The generative model G is set be soundary-seeking generative adversarial network (BEGAN).
The BEGAN architecture is summarized as follows] 11 The generator has latent dimension A = 62 and four layers. The first two are fully connected layers with the architecture 62 1024 6272, and with ReLU activation functions. The output of the second layer, reshaped to 128 x 7 x 7, forwarded to a deconvolution layer with kernel size and stride 2. The third layer uses ReLU activations and has output size 64 x 14 x 14, where 64 is the number of channels. The fourth layer a deconvolution layer with kernel size and strides and it uses ReLU activations and has output size 1 x 28 x 28, where the number of channels is 1.
The BEGAN is trained with a mini-batch size of 256, a learning rate of 0.0002, and 100 epochs. The other parameters are the same as those for the MNIST dataset. We perform two sets of experiments, considering the spiked covariance and phase retrieval models separately. The corresponding results reported in Figures 4 5 6 and [ From these figures, again, we can observe clear superiority of PPower r to Power and TP PPower. We note that for the Fashion-MNIST dataset, some of the images are not sparse in the natural basis, but we observe from Figures and 6 that even for the sparsest images (sandals), PPower also significantly outperforms TPower.
Further details of the architecture can be found at htttps://g thub. www..hc...h....c.cc com/hwa suk eee/ tensorf1 oww www.geeeratiiooo vee mode-moeelcc lectiont
23

---

Published as a conference paper at ICLR 2022
(a) 3 1 and m
200
(b) 8 and
100
Figure 4: Examples of reconstructed Fashion-MNIST images for the spiked covariance model.
0.8
0.6
Cannemitaatt
Pond Trcwer PILNO
Ticme
200
500
2.0
2.5
3.0
(a) Fixing 8 1 and varying
(b) Fixing m 300 and varying /
Figure 5: Quantitative comparisons of the performance of Power, TPower and PPowe according to the Cosine Similarity for the Mishion-MNIST dataset and the spiked covariance model.
(a) m 200
(b) m 400
Figure 6: Examples of reconstructed images the Fashion-MNIST dataset for phase retrieval.
5.5
Tower
Codra
522
Figure 7: Quantitative comparisons of the performance of Power, TP fPower and PPower according to the Cosine Similarity for the Fashion-MNIST dataset and the phase retrieval model.
24

---

Published as a conference paper at ICLR 2022
Teouee Power Ohigral
Phase Troeert TheA Tewer Oligral
Phoner
(a) 3
and 6000
(b) 8
3000
Figure 8: Examples of reconstructed CelebA images for the spiked covariance model.
0.8
Cosine Similarity
Cosine Similarity
0.6
Power
Power TPower
TPower
0.4
0.4
TPowerW PPower
TPowerW
PPower
0.2
0.2
0.0
0.0
2000
4000
6000 m
8000
10000
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
B
(a) Fixing 3 = 1 and varying m
(b) Fixing m = 3000 and varying 8
Figure 9:
Quantitative comparisons of performance of Power, TPower, TPowerW and PPower according to the Cosine Similarity for the CelebA dataset and spiked covariance model.
I NUMERICAL. RESULTS FOR THE CELEBA DATASET
The CelebA dataset consists more than 200, 000 face images of celebrities, where each input image is cropped to 64 x 64 RGB image with 64 x 64 x 3 = 12288. The generative model G is set to be a pre-trained Deep Convolutional Generative Adversarial Networks (DCGAN) model with latent dimension 2017) directly. We select the best estimate among 2 random restarts. The Adam optimizer with 100 steps and learning rate of 0.1 is used for the projection operator.
100. We the DCGAN model trained by the authors of (Bora al.,
For the images of the CelebA dataset, the corresponding vectors are clearly not sparse in the natural basis. To make fairer comparison the sparsity-based method TPower, convert the original images to the wavelet basis, and perform TPower on these converted images. The obtained results of TFower is denoted by TP TPoweeR, with "W" referring to the conversion to images in the wavelet basis. In each iteration of TPower and TPowerW, the calculated entries are truncated to zero except for the largest & entries. For CelebA, q is set to be 2000. Other parameters are the same those for the MNIST dataset. We also perform two sets of experiments, considering the spiked covariance and phase retrieval models separately. The corresponding results reported in Figures and 9 From these figures, we can observe the superiority of PPower to Power, TP Foower and TP Powerr, whereas TPowerW only marginally improves over TPower.
then converted back the vectors in the natural basis. The corresponding method
25


Reviews:
[{"review_id": "pEtqv2TBBwC", "reviewer": "Reviewer_4eD5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1. I think this paper does good work in its attempt to characterize both, and succeeds in characterizing the second **under a good initialization**. \n2. Prior work either made assumptions on the type of GAN (such as being randomly initialized) or had algorithms that seemed not very practical. It is nice to see a potentially practical result in a more general setting, even if it relies on good initialization. \n\nWeaknesses: \n1. I am curious to see if GANs in practice satisfy lipschitzness, in particular the GAN that was used in the experiments. It would be nice to see some experiments to this effect. \n2. I think the experiments are interesting and demonstrate (at least naively) that PPower is good. I would be interested in looking at the performance of TPower (the truncated power method, where you zero out all but the largest k entries) for these images in the *wavelet basis*, since that is where the method is more natural (since images are conjectured to be sparse in this basis). \n\n", "summary_of_the_paper": "This paper studies the problem of PCA with a generative model setup. More precisely, they study the following setting \nGiven $\\overline V = V + E$ where $V$ is PSD and $E$ is a perturbation matrix, find $\\text{max}_w~ w^T V w$ where $w \\in \\text{Range}(G)$ where $G : B_2^k(r) \\rightarrow \\mathbb S^{n-1}$ is $L$-lipschitz.  \n\nThe algorithm they analyze is a projected power method (PPower), similar to iterative hard thresholding for the case when $w$ is sparse. They demonstrate that if $w^{(i)} $ for $i \\leq t$ are the $w$'s at each iteration, then for $Q(x) = x^T V x$, $Q(w^{(i)})$ is monotonically non-decreasing. \n\nThe subsequent results rely on the following two assumptions, which the authors demonstrate in the setting of the spiked wigner model, spiked covariance model and phase retrieval.  \n\nA. There is a gap between the largest and second largest eigenvalue of $\\overline V$. \nB. For $S_1, S_2 \\subset \\mathbb R^n$ satisfying $m = \\Omega( \\log(|S_1| \\cdot |S_2|))$, for all $s_i \\in S_i$, $|s_1^T E s_2| \\leq C \\sqrt{\\frac{ \\log(|S_1| \\cdot |S_2|)}{m}} \\cdot \\|s_1\\| \\cdot \\|s_2\\|$. \n\nThe authors then provide guarantees for the optimizer in the context of these three settings, under these assumptions. More precisely, if $\\overline v$ is the global optimizer, $\\overline x$  is the true hidden signal, $x_G$ is the closest point in the range of the GAN to $\\overline x$ and $\\Delta = \\overline \\lambda_1 - \\overline \\lambda_2$ is the gap between the largest and second largest eigenvector of $\\overline V$, they show, \n$ \\min \\{\\|\\overline x - \\overline v\\|, \\|\\overline x + \\overline v\\| \\} \\leq O(\\sqrt{k \\log(Lr/\\delta)/m}/\\Delta) + 4(\\overline \\lambda_1/\\Delta) \\cdot \\|x_G - \\overline x\\| + O(\\delta n / m \\Delta)$\n\nAdditionally, they demonstrate conditions on the initial $w_0$ which is input to PPower under which the algorithm has a linear rate of convergence, however they also need certain other assumptions which are satisfied in natural settings (such as the range of the GAN being positive). \n\nFinally, they demonstrate experiments on MNIST for the spiked covariance model where they compare their algorithm (PPower) to the truncated power method (TPower) and the vanilla power method as a baseline. They show that the performance of PPower is much greater. \n\n\n\n", "summary_of_the_review": "I think this is an interesting paper and vote to accept it, though it would be nice to see the experiments for the questions I've asked. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jinRjZtXTo", "reviewer": "Reviewer_kCBb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\n1) The problem is important and well-stated. The paper is clearly written. Theoretical and algorithmic developments that can move the needle away from sparsity-based assumptions are very much needed, and this paper can be an interesting development in that direction.\n\n2) The assumptions and the theoretical results are plausible. \n\nWeakness:\n\n1) My biggest concern is theoretical, and a little bit philosophical. From what I can tell, the generative model $G$ is trained \\textit{on the same data} for which the eigenvector computation is desired. This implies that the training of $G$ and its performance is not independent, and this undercuts the theoretical results presented in a major way. Additionally, this can result in the \"Richard Feynman's license plate\" phenomenon (see \\url{https://www.quora.com/Richard-Feyman-had-once-remarked-about-an-amazing-experience-where-he-saw-a-car-with-the-license-plate-ARW-357-Did-it-have-any-significance?share=1} for a \npop-science version) or statistical superefficiency, which results in underestimation of uncertainty and false precision/accuracy in other contexts. \n\nAlso, it is not fair to compare PPower with G trained on the same data with other algorithms that do not use such additional information.  \n\nThis issue can be taken care of by partitioning the data to ensure that the training of G and the PPower computations are independent, but that would be a major revision of this paper as it stands now.\n\n[REVISED COMMENT:] Based on the author's response, I think my main concern with this paper (stated above) is addressed. \n\n2) A second major issue is computational. How expensive is the pre-training of G followed by PPower compared to rival algorithms? My guess is that it would be substantially more expensive, since learning $G$ is a very expensive step. \n\n3) Authors have done a reasonable review of the literature on sparse PCA, but missed those that try to balance statistical efficiency with computational complexity, see Wang et al, Annals of Statistics, 2016, pages 1896-1930 and related papers (there are papers before and after this one on this topic). I think the authors will find the PPower scheme is very high on statistical efficiency, which is a good thing, but requires detailed discussion.\n\nAlso, the above reference and related papers will give authors ideas about more efficient algorithms for the case when the leading eigenvector is actually sparse: the Power and TPower algorithms are essentially strawmen. \n", "summary_of_the_paper": "Principal component analysis (PCA) is one of the most commonly used techniques for dimension reduction in data and for explaining variability of the data in terms of its eigenvalues/vectors. Unfortunately in high-dimensions, PCA is mathematically inconsistent: this is well-known from random matrix literature. Hence the standard approach happens to be to assume that there is sparsity in the leading eigenvectors. In this paper however, motivated by Bora et. al (2017), the study is based on the conjecture/premise that sparsity assumption may be replaceable by the assumption that the leading eigenvector is close to the range of a deep generative model.  \n", "summary_of_the_review": "The problem is important and the idea of replacing sparsity with a generative model is very interesting. However, technical concerns remain.  \n\n\nRevised comment: I think the authors' for their detailed and pertinent responses to comments. My major concerns are now addressed, and I am happy to assign an imporved score. I think this paper can be a major contribution, and I agree with the authors that some of the criticisms (for example, on computations) that can be leveled at this paper are relevant to the entire gamut of papers following Bora et al. Since there is no free lunch, I am willing to accept the argument that there must be a bit of give in terms of training cost or some toher tings to obtain this new kind of PCA. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XQ5jtVo1UE8", "reviewer": "Reviewer_itua", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The PCA problem under Generative priors studied here is a generalization of the standard PCA problem, and also a generalization of the cone-constrained PCA problem studied in [1].  I believe that studying PCA and the power iteration beyond convex settings (such as [1]) is well-motivated.  Since projection onto a general non-convex set is a computationally hard problem in general, this work assumes access to a black-box oracle that can project points to arbitrary non-convex sets.  Therefore, the main theoretical results of this work are of statistical nature: a bound on the sample complexity of the global maximizer of the constrained problem and a sample complexity analysis of power iteration (assuming that perfect projections to the non-convex set can be performed efficiently).  \n\nThe first theoretical result (Theorem 1) (bounding the sample complexity of the global maximum) does not look very surprising to me: it uses the fact that the range of $L$-Lipschitz generative $G$ model has a small cover and relies on standard concentration/cover arguments. \n\n The convergence result of the power iteration (Theorem 2)  is more interesting as, even with a perfect projection oracle, the power iteration over general non-convex sets would not converge to the global maximum (constrained in the non-convex set).  The authors have some additional assumptions in order to prove convergence: namely that they initialize the iteration at some point that correlates well with the optimal solution $\\bar{x}$, i.e., $\\bar{x}^T w^{(0)} \\geq \\nu >0$.  The authors state that a similar assumption was used in [1] to prove convergence when the constrained set is a convex cone.  Under these assumptions it is not entirely clear to me whether the convergence proof presented here differs significantly from the prior work.  Given the above, I am leaning towards rejection of this work but I am willing to reconsider if the authors or other reviewers can show otherwise.\n\nFeedback/Questions:\nI think it would be beneficial if the authors compare their convergence analysis (Lemma 2, Theorem 2) with that of [1] (or other related prior work) and highlight the main differences/challenges of the non-convex setting (given the assumptions) analyzed here.\n\n[1]: Yash Deshpande, Andrea Montanari, and Emile Richard. Cone-constrained principal component\nanalysis. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), pp. 2717–2725, 2014.\n", "summary_of_the_paper": "This work studies PCA under the contraint that the principal eigenvectors lie in the range of some fixed generative model, e.g., a neural network with fixed weights.  More precisely, given an $L$-Lipschitz function $G : \\mathbb R^k \\mapsto R(G)$ the authors try to find a vector $w \\in R(G)$ that maximizes $w^T V w$, where $V = \\bar{V} + E$, is a (noisy) version of the \"true\" psd matrix $\\bar{V}$.  The corresponding true solution $\\bar{x}$ is defined to be the top eigenvector of $\\bar{V}$.\n\nThey assume that the range $R(G)$ of $G$ is a subset of the unit ball of $\\mathbb R^n$ and that the error matrix $E$ is not too large in the sense that for any sets $S_1, S_2$ with $m = \\Omega( \\log( |S_1| |S_2|))$ it holds that $|s_1^T E s_2| \\leq \\sqrt{ \\log(|S_1| |S_2|)/ m} \\|s_1\\|_2 \\|s_2\\|_2$.  This error bound is satisfied (via standard concentration inequalities) by the spiked covariance and phase retrieval model assuming that the number of samples $m$ is large enough.\n\nThe authors show two main results.  First, they show that under the above assumptions the global maximizer given the noisy matrix $V$, i.e., the maximizer $\\hat{v}$ of $w^T V w$ constrained on $R(G)$ has error roughly $\\|\\hat{v} - \\bar{x}\\|_2 \\leq \\sqrt{k \\log L/m}$.  Next, they show that the power iteration algorithm together with a projection step onto the contraint set $R(G)$ will also eventually converge to a vector with similar error.  They also give experimental results showing that adding this projection step in the power iteration leads to improved recovery for the spiked covariance and phase retrieval problems for the MNIST and Fashion-MNIST datasets in the case where the generative model $G$ is a pre-trained variational autoencoder of small latent dimension $k$.", "summary_of_the_review": "Strengths:  The paper studies an important and well-motivated problem and provides sample complexity bounds for an interesting setting. Overall, the paper is well-written and the main results and contributions are cleanly stated.\nWeaknesses: The first theoretical result does is not very surprising and its proof is rather standard.  It would also be good to discuss the technical novelty of the second theoretical result and compare it with the prior work.\nGiven the above, I am leaning towards rejection of this work but I am willing to reconsider if the authors or other reviewers can show otherwise.\n\n ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies PCA under a generative model setup. The authors analyze the projected power method in a range of natural settings.
Moreover, experimental evaluation and comparison to other methods is performed on MNIST. The paper studies an important problem. Despite some initial concerns, the reviewers overall agreed that this is an interesting contribution. I recommend acceptance.
Decision: Accept (Poster)