Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the randomised SVD algorithm with non-standard Gaussian vectors which is then used to approximate Hilbert-Schmidt operators using a new kernel based on out products of weighted Jacobi polynomials.
main_review: 
0) In abstract: "Here, we generalize the theory of randomized SVD to to multivariate Gaussian vectors, [...]"

- A theory of randomized SVD already exists for multivariate Gaussian vectors though? Furthermore, read 1). 

1) "Generalization 1 [...]"

- This bit is unclear. It seems like the authors are claiming to generalise the randomised SVD for Gaussian vectors with non-identity covariance. However, in the beginning of Sec 3 this was already developed by Boulle & Townsend 2021. I guess what is meant is that new theoretical results pertaining to the approximation error are obtained? I would expect this to be more clear in a  camera-ready version. Also I guess this is the same issue as in abstract (point 0) above). 

2) "In particular, this highlights that a suitably chosen covariance matrix can outperform the randomized SVD with standard Gaussian vectors"

- Does the converse hold as well? i.e. can an ill-suited covariance matrix make the algorithm worse?

3) "Therefore, each column of \Omega is an object, consisting of a polynomial representation [...]"

- Why polynomials instead of something else? 

4) Bad figure ordering / Layout.

-The first Figure to be references is Fig. 4 (rather than 1) on page 4. However, the actual figure does not appear until page 9. 

5) Bad notation.

-L is used both to denote the Cholesky factor of a kernel and the space of square integrable functions. E.g. L^2(D) could be interpreted as the square of the Cholesky factor evaluated at D. 

6) Bad enumeration notation. In the first paragraph of page 5 items are enuemrated as (1), (2), and (3). However this is the same notation used to reference numbered equations making the paragraph quite hard to read. 

7) "A desireable property of a covariance kernel is to be unbiased towards one spatial direction"

-This would require further motivation. Would it not depend on application / prior knowledge of the problem? 

8) "[...], we observe a large variation of the randomly generated functions near x = \pm 1, [...]"

-Upon examining Figure 1 it seems to me the opposite is true, i.e. the largest variation is found in mid-interval while it is the smallest at the end-points. Please clarify. 

9) Figure 2. 

- I believe the authors might get their point across better if (additionally) the error is plotted vs time. 

10) Proofs. 

- The proofs would be easier to follow if the authors actually state what results they are using in their arguments instead of e.g. just referencing (Halko et al, 2011 Prop A.1). 

11) Proof of Lemma 7. 

-It is not stated what is used how to retrieve the upper bound of the moment generating function. 

12) Proof of Theorem 2. "[...] combining (Boulle & Townsend, 2021, Thm 3.2) and Lemma 7 in Equation (10) [...]"

- Lemma 7 is not given in Equation (10). Also the proof would be more readable if the result by Boulle and Townsend was stated in the text. 

13)  


summary_of_the_review: While the paper appears to adduce some novel results. However, the presentation is unclear which makes it hard to verify the results of the authors and properly situate it in the context of previous literature. 

I do however think that the authors have a reasonable chance to address my concerns for a camera-ready version, why I recommend a marginal accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes and analyzes a generalization of the randomized SVD to incorporate any covariance matrix and to Hilbert-Schmidt operators. Extensive numerical experiments further strengthen the case for this generalization.
main_review: Randomized Singular Value Decomposition (SVD) is an important algorithm in the field of numerical linear algebra. Suppose $A \in \mathbb{R}^{m \times n}$ is a large matrix. It is often the case that although $m$ and $n$ are large, the rank of the matrix $A$ is small, and therefore a low rank approximation $A \approx B C$ for $B \in \mathbb{R}^{m \times k}$ and $A \in \mathbb{R}^{k \times n}$ and $k \ll \min(m,n)$ is desired. Randomized SVD computes a rank-$k$ approximation for $A$. The recipe for doing that is to first compute an approximate basis for the range space of $A$. Specifically, we want an orthonormal matrix $Q \in \mathbb{R}^{m \times k}$ such that $A \approx Q Q^* A$. Randomized SVD does this by letting $\Omega \in \mathbb{R}^{n \times k}$ be a matrix whose entries are i.i.d. standard Gaussian, and then letting $Q$ be the orthonormal matrix from the QR-decomposition $Q R = A \Omega$. Once we have $Q$, we have a low rank approximation $A \approx Q B$ for $B = Q^* A$. The next step is to compute the SVD of the small matrix $B = \tilde{U} \Sigma V*$, which finally gives the approximate SVD for $A$ as $U \Sigma V^*$ for $U = Q \tilde{U}$.

This paper starts by first generalizing the above recipe by letting the columns of $\Omega$ to be sampled from a multivariate Gaussian distribution with a general covariance matrix $K \in \mathbb{R}^{n \times n}$. The error $\lVert A - Q Q^* A \rVert_F$ is upper bounded, which is similar to the upper bound in vanilla Randomized SVD. Then this method is also generalized to approximation of Hilbert-Schmidt operators $\mathscr{F}$, instead of matrices $A$. The samples are now coming from a Gaussian process with a covariance kernel $K$. As is expected, the approximation quality of the randomized algorithms is closely tied to the spectrum of the covariance matrix/kernel $K$. To this end, some intuition is provided for the relation between the choice of the covariance kernel and the approximation ability of the algorithm. Finally, numerical experiments provide justification for these generalizations by showcasing their power.

The only minor complaint about the paper is that the presentation could be made less terse, especially in Section 3.1 where Randomized SVD for Hilbert-Schmidt operators is discussed. For example, it would be nice to provide some background on how QR algorithm is used on $Y$ to get $Q$, or why each column of $\Omega$ consists of "polynomial representation of a smooth random function sampled from the GP in the Chebyshev basis". It's also unfortunate that no results are provided for the approximation errors in the case of Hilbert-Schmidt operators.

I also didn't understand why the quantity $\gamma_k$ measures "the quality of the covariance kernel $K$ in $\mathcal{GP}(0, K)$ to generate random functions that can learn the H-S operator $\mathscr{F}$" claimed in Section 4.2.
summary_of_the_review: The paper should be accepted because it is well-written for the most part, tackles an important problem, and provides a novel generalization of a well-known method.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a generalization approach for the randomized SVD. In the existing approach of the randomized SVD, a standard Gaussian random matrix is used to reduce the size of a matrix to perform SVD. The proposed approach uses a multivariate Gaussian distribution with a covariance matrix instead of the standard Gaussian random matrix in performing SVD. Since the covariance matrix can reflect prior knowledge of the given matrix, the proposed approach can improve the approximation quality of the randomized SVD. By using a synthetic dataset, this paper conducts experiments to show the effectiveness of the proposed approach.
main_review: Basically, I like the paper's motivation; it is quite a fundamental research problem to reduce computational time by using randomized SVD and improve its approximation quality. Besides, this paper is well structured, and the theoretical background of the proposed approach is well described in the paper. However, I have the following several concerns to the paper:

In the experiments, it uses only synthetic datasets. Therefore, it is unclear whether the proposed approach is useful for real applications. Typically, if the given matrix is dense, singular values decay rapidly. If the given matrix is sparse, singular values decay slowly. I want to know whether the proposed approach can achieve high approximation accuracy for various types of matrices. 

In the experiment of Figure 2, it seems that the computational time of the Cholesky factorization is not included. I think this is not a fair comparison to the previous approach. Since the computational cost of the Cholesky factorization is cubic according to the size of the covariance matrix, the proposed approach would need a large computational time for the Cholesky factorization. In contrast, the previous approach does not need to compute Cholesky factorization. I want to know the end-to-end computational times of the proposed and previous approach for the specific target rank of SVD. 
In terms of computational time, the paper should show the theoretical computational cost of the proposed approach. 

As for the approximation quality, the previous approach, as well as the proposed approach, can more accurately perform SVD as the oversampling parameter increases. So, I think the paper should show the experimental results of the approximation quality of each approach against the oversampling parameter. The setting of the oversampling parameter in the experiments is unclear from the descriptions of the paper. 
summary_of_the_review: This paper is well-written. 
Real datasets should be used in the experiments. 
The computational time of the Cholesky factorization should be included in Figure 2.
review_title: null

Meta-review: This paper studies a generalization of the randomized SVD algorithm with non-standard Gaussian vectors, which is then used to incorporate any covariance matrix and to Hilbert-Schmidt operators.  It uses a new kernel related to products of weighted Jacobi polynomials; and extensive numerical experiments further strengthen the case for this generalization.  Reviewers had initial concerns that were addressed, and the method should be of broad interest.
Decision: Accept (Poster)