Generalized Eigenvalue Problems with Generative Priors

Thank you for your helpful feedback and comments. Our responses to the main concerns are given as follows.

(Assumption 2.4 looks too strong and not very convincing. At the first sight, I don't see any pair $(\mathbf{E}, \mathbf{F})$ which satisfies this assumption except the trivial one $\mathbf{E} = \mathbf{0}$ and $\mathbf{F} = \mathbf{0}$. Please find at least one class of $(\mathbf{E}, \mathbf{F})$ which satisfies this assumption) As stated in the paragraph preceding Assumption 2.4, similarly to the proof for the spiked covariance model in [45, Appendix B.1], it can be readily demonstrated that for the $(\hat{\mathbf{A}}, \hat{\mathbf{B}})$ constructed in Section 4.2, the corresponding perturbation matrices $\mathbf{E}$ and $\mathbf{F}$ satisfy Assumption 2.4 with high probability. More specifically, for Eq. (29) with $\hat{\mathbf{A}} = \frac{1}{m}\sum_{i=1}^m(2\gamma_i\mathbf{v}^*+\mathbf{z}_i)(2\gamma_i\mathbf{v}^*+\mathbf{z}_i)^\top,$

and $\hat{\mathbf{B}} =\frac{1}{m}\sum_{i=1}^m \mathbf{w}_i\mathbf{w}_i^\top$, we have $\mathbb{E}[\hat{\mathbf{A}}] = 4\mathbf{v}^*(\mathbf{v}^*)^\top + \mathbf{I}_n$ and $\mathbb{E}[\hat{\mathbf{B}}] = \mathbf{I}_n$;

where $\mathbf{v}^*$ is a unit vector; $\gamma_i \sim \mathcal{N}(0,1)$, $\mathbf{z}_i \sim \mathcal{N}(\mathbf{0},\mathbf{I}_n)$, $\mathbf{w}_i\sim \mathcal{N}(\mathbf{0},\mathbf{I}_n)$, and they are mutually independent. If setting $\mathbf{A} = \mathbb{E}[\hat{\mathbf{A}}]$ and $\mathbf{E} = \hat{\mathbf{A}} - \mathbf{A} \neq \mathbf{0}$, and setting $\mathbf{B} = \mathbb{E}[\hat{\mathbf{B}}]$ and $\mathbf{F} = \hat{\mathbf{B}} - \mathbf{B} \neq \mathbf{0}$, we obtain for any $\mathbf{s}_1 \in S_1$, $\mathbf{s}_2 \in S_2$,

$\left|\mathbf{s}_1^\top \mathbf{E} \mathbf{s}_2\right|$

$= \left|\frac{1}{m}\sum_{i=1}^m \left(\mathbf{s}_1^\top(2\gamma_i\mathbf{v}^*+\mathbf{z}_i) \cdot \mathbf{s}_2^\top(2\gamma_i\mathbf{v}^*+\mathbf{z}_i) - \mathbb{E}\left[\mathbf{s}_1^\top(2\gamma_i\mathbf{v}^*+\mathbf{z}_i) \cdot\mathbf{s}_2^\top(2\gamma_i\mathbf{v}^*+\mathbf{z}_i)\right]\right)\right|.$

Since $\mathbf{s}_1^\top(2\gamma_i\mathbf{v}^*+\mathbf{z}_i) \mathbf{s}_2^\top(2\gamma_i\mathbf{v}^*+\mathbf{z}_i)$ are sub-exponential and independent (with the sub-exponential norm being upper bounded by $C\\|\mathbf{s}_1\\|_2\cdot \\|\mathbf{s}_2\\|_2$, where $C$ is an absolute constant), using the concentration inequality for the sum of independent sub-exponential random variables [75, Proposition 5.16], we obtain for any $u > 0$ satisfying $m = \Omega(u)$, the following holds with probability $1-e^{-\Omega(u)}$:

$\left|\mathbf{s}_1^\top \mathbf{E} \mathbf{s}_2\right| \le C \\|\mathbf{s}_1\\|_2\cdot \\|\mathbf{s}_2\\|_2 \cdot\sqrt{\frac{u}{m}}.$

Taking a union bound for all $\mathbf{s}_1 \in S_1$, $\mathbf{s}_2 \in S_2$, and setting $u = \log (|S_1|\cdot |S_2|)$, we obtain with probability $1-e^{-\Omega(\log (|S_1|\cdot |S_2|))}$ that the following holds for all all $\mathbf{s}_1 \in S_1$, $\mathbf{s}_2 \in S_2$:

$\left|\mathbf{s}_1^\top \mathbf{E} \mathbf{s}_2\right| \le C \\|\mathbf{s}_1\\|_2\cdot \\|\mathbf{s}_2\\|_2 \cdot \sqrt{\frac{\log (|S_1|\cdot |S_2|)}{m}}.$

Please refer to [45, Appendix B.1] for more technical details. Similarly, for $\big|\mathbf{s}_1^\top \mathbf{F} \mathbf{s}_2\big|$, we can obtain the upper bound in Eq. (7).

(It looks not interesting to only put three conditions (21), (22), (23) in Theorem 3.3 but don't identify (at least) a class of matrices $(\mathbf{A}, \mathbf{B})$ which satisfies these conditions. It is more interesting if $\mathbf{B}$ is not the trivial one, i.e., $\mathbf{B}=\mathbf{I}_n$, as in the experiment since you are considering the generalised eigenvalue problem) We have deliberated in Remark 3.4 regarding when the three conditions are satisfied. Specifically, we demonstrate that when $\kappa(\mathbf{B}) = \lambda_{\max}(\mathbf{B})/\lambda_{\min}(\mathbf{B})$ is close to 1 (or more precisely, $\kappa(\mathbf{B})<c’$ for some constant $c’>1$; note that we do not make any attempt to refine the constant $c'$ here, and we believe that our theorem actually holds under a more relaxed condition), the three conditions can be satisfied. Since this work is primarily theoretical, we follow [8] to only conduct the experiments for the case where $\mathbf{B}=\mathbf{I}_n$. We have added the experiments for the case that $\hat{\mathbf{B}}$ in Eq. (29) is modified by $\mathbf{w}_i \sim \mathcal{N}(\mathbf{0}, \mathrm{Diag}(2,1,\ldots,1))$ (other settings of the experiments remain unchanged), and thus $\mathbf{B} = \mathbb{E}[\hat{\mathbf{B}}] = \mathrm{Diag}(2,1,\ldots,1)$ and $\kappa(\mathbf{B}) = 2$. The quantitative results are as follows:

From the above results, we observe that our PRFM method also performs well in this case. We will incorporate the corresponding numerical results in the revised version.

(Typos) Thanks for pointing out these typos. In the revised version, we will correct them and meticulously check the manuscript to prevent typos.

Thank you for your recognition of this paper as well as the beneficial comments and questions. Our responses to the major concerns are as follows.

(Theoretical analysis taking the approximation into account would be good to see) Similar to previous works such as [45, 59, 65], we assume exact projection in the theoretical analysis. We agree that theoretical analysis taking the approximation into account is an intriguing direction and we leave it for future research.

(Even with the current approximate projection based off gradient descent, I would like to see how the proposed algorithm compares in compute time to other methods such as PPower) The projection step onto the range of the generative model occupies the majority of the running time of the algorithm. Consequently, the compute time of PRFM is approximately the same as PPower, with only a minor increase due to more matrix-vector multiplications in each iteration. In the following table, we present the running time (in seconds) for PRFM and PPower on MNIST with $\hat{\mathbf{A}}$ and $\hat{\mathbf{B}}$ generated from Eq. (29) (and the number of iterations for both algorithms is set to 10; the running time is averaged over 10 test images and 10 restarts). Note that we run the algorithms given $\hat{\mathbf{A}}, \hat{\mathbf{B}} \in \mathbb{R}^{n\times n}$ (or $\mathbf{V} \in \mathbb{R}^{n\times n}$ for PPower), and the running time will not increase with $m$.

(Achieving $\nu_0$ close to 1 itself seems like a hard problem since it would imply that you already have a pretty good initialization to start with, which may be hard to find in high dimensions) Thanks for the comment. While this initialization condition might seem restrictive, it seems to be the mildest initialization condition that we can assume for the case of generative priors. The reason is as follows: For sparse priors, the initialization vector can be obtained via a convex program (see [72]). Regrettably, for a generative model, this idea no longer applies since, without additional assumptions, the problem cannot be relaxed to a convex optimization problem. We observe that similar initialization conditions have been imposed in previous works such as [31, 45]. Additionally, in practice, we do not enforce such an initialization condition to hold and we discover that simply setting the initial vector to be $[1,1,\ldots,1]^\top/\sqrt{n} \in \mathbb{R}^n$ in the numerical simulations performs well.

(Apart from the numerical experiments pointed out in the paper, are there other scenarios where assuming the existence of such generative priors is reasonable/well-accepted) From the successful applications of deep generative models in diverse fields, there are various scenarios where assuming the existence of such generative priors is reasonable and well-accepted. For instance, robust compressed sensing MRI with generative priors has been investigated in

Jalal, A., Arvinte, M., Daras, G., Price, E., Dimakis, A.G. and Tamir, J., 2021. Robust compressed sensing MRI with deep generative priors. Advances in Neural Information Processing Systems, 34, pp.14938-14954.

Additionally, an approach similar to the closely related PPower method has been applied to Interferometric Passive Radar Imaging in

Kazemi, S., Yonel, B. and Yazici, B., 2023. Interferometric Passive Radar Imaging With Deep Denoising Priors. IEEE Transactions on Aerospace and Electronic Systems, 60(1), pp.145-156.

For more real applications of deep generative models in inverse problems in imaging, please refer to the following popular survey paper [569 citations]:

Ongie, G., Jalal, A., Metzler, C.A., Baraniuk, R.G., Dimakis, A.G. and Willett, R., 2020. Deep learning techniques for inverse problems in imaging. IEEE Journal on Selected Areas in Information Theory, 1(1), pp.39-56.

(Outside the spiked covariance model, can the authors specify other covariance matrices where Assumption 2.4 is satisfied) Assumption 2.4 is also satisfied with high probability by the matrices corresponding to the phase retrieval model (see Eq. (30)). Additionally, similar to what is mentioned in [72], it is straightforward to verify that under generative priors, for various statistical models that can be formulated as a GEP such as CCA and FDA, Assumption 2.4 will be satisfied with high probability.

Thank you for your helpful feedback and suggestions. Our responses to the main concerns are given as follows.

(The presentation of the problem could be improved) Thank you for the comments. We will undertake revisions on the presentation, encompassing the following aspects: 1) Mention that Eq. (3) is a Rayleigh quotient; 2) Relocate Section 2.2 to the Appendix; 3) Incorporate more explanations for the derivation of Algorithm 1; 4) Include Section C of the Appendix in the main paper (and we will meticulously modify it to prevent overstated claims).

(The numerical experiments are carried out on toy data and it makes it difficult to understand how it could be used in practice) We have also conducted the experiments for the CelebA dataset (which comprises over 200,000 face images of celebrities and the image vector has a dimension of $n = 64 \times 64 \times 3 = 12288$) in the case where $\hat{\mathbf{A}}$ and $\hat{\mathbf{B}}$ are generated from Eq. (29), and the quantitative results (in terms of Cosine Similarity) are as follows.

We will incorporate the experimental results on the CelebA dataset in the revised version.

(I am not quite sure to understand how the generative prior (and the projection onto the range of a pre-trained model) is not redundant with the optimization problem itself) The generative prior is not redundant with the optimization problem. The rationale is as follows: We concentrate on the high-dimensional scenario where the number of samples $m$ is significantly smaller than the data dimension $n$. To attain reliable reconstruction in this context, it is necessary to impose a low-dimensional prior on the underlying signal and add the corresponding constraint (or regularization) to the optimization problem. A common selection for the data prior is the sparse prior (note that for the popular sparse PCA/GEP problem, the constraint corresponding to the sparse prior also needs to be imposed, as seen in Eq. (5)). Given the numerous successful applications of deep generative models, we are aware that generative priors can be far more potent in modeling the distribution of real data. Hence, we follow [4] that considers generative priors for the underlying signal, and impose the corresponding constraint into the optimization problem.

(Is there any impact of the condition $\gamma_1 + \gamma_2 < 2$ ? Is it a reasonable constraint?) The condition $\gamma_1 + \gamma_2 < 2$ can be expressed as $\eta (\lambda_1 -\lambda_2)\lambda_{\min}(\mathbf{B}) + \eta (\lambda_1 -\lambda_n)\lambda_{\max}(\mathbf{B}) < 2$, where $\lambda_1 > \lambda_2 \ge \ldots \lambda_n$ are the generalized eigenvalues of $(\mathbf{A}, \mathbf{B})$. This is a reasonable constraint that is similar to the constraint $\eta \lambda_{\max}(\mathbf{B}) < 1/(1+c)$ in [72, Theorem 1] (where $c > 0$ is a constant specified in [72, Assumption 1]). More precisely, note that $\eta/\rho_{t-1}$ in [72, Algorithm 1] plays the role as our $\eta$ and $\rho_{t-1} \approx \lambda_1$. Then, if employing our notation, the constraint in [72, Theorem 1] is approximately $\eta \lambda_1 \lambda_{\max}(\mathbf{B}) < 1/(1+c)$, whose impact is to impose an upper bound on the selection of the step size $\eta$.

(How does the approximation of the projection step impact the algorithm and the numerical results?) Since the projection step cannot be exact in the experiments, we adhere to previous works such as [45, 59, 65] and employ a gradient descent method along with the Adam optimizer to approximately carry out the projection step. From the experimental results, we observe that the approximation of the projection step proves effective as we are able to obtain reasonably good reconstructions when the number of samples $m$ is significantly smaller than the data dimension $n$.

(How stable is it when $k$ grows ? (As it is known to behave poorly as $k$ grows). One possible solution could be to solve the problem as the $\max_{\mathbf{U}}\mathrm{Tr}(\mathbf{U}^\top\mathbf{A}\mathbf{U})$ with $\mathbf{U}$ in a generalized Stiefel manifold (defined with $\mathbf{B}$) and the generative prior could be enforced with a regularization) In our experiments, we employ a pre-trained generative model with the latent dimension $k$ remaining fixed. For instance, for the generative model pre-trained for the MNIST dataset, $k = 20$, and for the generative model pre-trained for the CelebA dataset, $k = 100$. We do not modify the generative model (and the latent dimension) as pre-training is time-consuming. Nevertheless, we are grateful to the reviewer for highlighting this intriguing optimization problem to us and we concur that it constitutes a promising direction for further investigation.

(Limitations and Ethics Review) Similar to the series of works following [4], we only conduct the experiments and pre-train the generative models for the publicly accessible and widely utilized datasets MNIST and CelebA. We believe that there should be no negative implication for the society and no requirement for an ethics review.

I thanks the authors for their answer which covers some of my concerns and I will raise my score.

About the limitations and ethics, although the authors only work on pre-trained models with classical dataset, they are tinkering with generative models. The implications for other generative models (on more sensitive data/applications) could be huge and it would deserve some discussion.