Fast Updating Truncated SVD for Representation Learning with Sparse Matrices

The paper is not always easy to read. For example, the contribution are hard to clearly assess at first even if they are detailled at the beginning of the paper.

I find on minor type in page 3: "Orthogonalzation" instead of "Orthogonalization".

-) It is not clear whether the superiority of the new algorithm, as evidenced by the numerical results, is natural or the result of inefficient comparisons. See my comments below. -) While the algorithmic contribution is non-trivial, the new algorithms are not really new since they follow what other published algorithms already do, albeit in a more efficient fashion.

This paper has two weaknesses I would like to discuss: issues of writing and grammar and potential numerical instabilities. I believe that the first of these can be addressed by revisions, and the second of these is an inherent (potential) limitation of the method that deserves a brief discussion by the authors in a revision.

Writing

This paper has several issues with writing and presentation.

Throughout, there are issues of grammar and English usage. The issues are numerous, but here are a few examples that stand out:

• The title and the first sentence of the abstract do not parse as grammatically correct.
• Several key phrases are ungrammatical: in many places, "truncated SVD" should be replaced by "the truncated SVD" (e.g., "updating truncated SVD" should be "updating the truncated SVD"). The "augment matrix" should be "augmented matrix". "Augment procedure" should be "augmentation procedure". Etc.
• There are other grammatical issues. For instance, consider the following sentence: "A series of methods that can be recognized as an instance of Rayleigh-Ritz projection has become a mainstream method owing to its high precision." The verb "has" should be changed to "have" as the subject of the sentence "series of methods" is plural. Similarly, "its" should be "their". Even with grammatical fixes, the sentences are difficult to read. A better version of the sentence would be as follows: "In the past twenty-five years, Rayleigh-Ritz projection methods have become the standard methods for updating the truncated SVD, owing to their high accuracy."

The grammatical issues are serious enough to make the paper more difficult to read and understand. I recommend the authors do thorough revisions of their paper to improve the grammar and English usage.

There are also structural and clarity issues with the writing. Again, there are many issues, of which we highlight a few:

• The phrase, "augment matrix" (which should be changed for grammar to "augmented matrix") appears in section 1 before that term is defined or even the problem stated.
• The authors state that they provide "RPI and GKL" variants of their algorithm in section 3.3, but these acronyms were defined only briefly earlier in section 3.1—a section I skimmed on my first reading. A backward reference GKL and RPI, e.g., "(see section 3.1)" would help readers.
• The precise meaning of isometric in lemma 3 is unclear.
• As far as I can tell, the average precision metric is never defined.

The paper could benefit from reorganization to improve the narrative and sequencing of ideas.

Lastly, there's an issue of framing of the truncated SVD updating problem. In section 2, the present the problem they're solving as "approximating the truncated SVD of $\overline{A} = [A,E]$". However, the problem that is really being solved is to compute (exactly) the truncated SVD of $[\hat{A},E]$, where $\hat{A} = U\Sigma V^\top \approx A$ is the truncated SVD of $A$. The original Zha–Simon procedure is very clear about this distinction, writing

Notice that in all the above three cases instead of the original term-document matrix $A$, we have used $A_k$, the best rank-$k$ approximation of $A$ as the starting point of the updating process. Therefore, we may not obtain the best rank-$k$ approximation of the true new term-document matrix."

I think the authors would benefit from this level of clarity about exactly what problem they are solving.

Overall, this paper would be greatly improved by rewriting to improve grammar and clarity.

Numerical Stability?

There are several aspects of the current proposal that are concerning from the standpoint of numerical stability. The proposed orthogonalization procedure uses the Gram–Schmidt process, which is well-known to suffer from potentially significant loss of orthogonality. Additionally, the updating rules decompose a matrix $U_k$ with orthonormal columns are the product of two matrices, both of which could become significantly ill-conditioned and resulting in stability degradations.

Assuming these stability issues are real, they are intrinsic limitations to the method; it's very unclear how these issues could be addressed while maintaining the method's competitive runtime. The numerical results suggest that the method is stable enough to remain useful for some data analysis tasks. I would like to see the authors comment on numerical stability in any revised version, just to mention this as a potential issue with the method.

This manuscripts largest weakness (and a significant one) is its lack of clarity in many respects. This spans the interplay with existing algorithms, the contribution, in what setting the proposed method is faster, and more. While the former two points could be addressed (though the manuscript does need significant reworking), the clarity around the appropriate settings for the algorithms, and therefore the contribution, is much less clear. This is most easily shown by illustration:

To choose one of the settings, let's consider updating (i.e., adding) columns to $A.$ In this case a QR factorization of $(I-U_kU_k^T)E$ is desired. The manuscript assumes $E$ is sparse, however the improvement is actually in a narrower regime. If $E$ has a constant number of non-zeros per row then nnz(E) is $\mathcal{O}(n)$ and the algorithms discussed in the manuscript are no more efficient than just forming $E - U(U^TE)$ and computing the dense QR factorization $\mathcal{O}(ns^2)$. So, the only setting of interest is if $E$ has a constant number of non-zeros per column, i.e., $\mathcal{O}(s)$ non-zeros. In this setting relatively few rows of $A$ receive updates. I don't know which setting is more/less common, but the manuscirpt lacks a clear articulation of such tradeoffs (including in the numerical experiments). This weakens the manuscript and makes it hard to understand what settings it applies to.

Similarly, it is not clear that most of section 3.1 is necessary. Bluntly it seems like an overly complicated build up of a simple choice. Considering the above setting, if $E$ has a constant number of non-zeros per column then why not just compute the Cholesky factorization $E^TE-(E^TU_k)(U_k^TE) = RR^T$ (which is \mathcal{O}(s^3) under this sparsity assumption) and then store the QR factorization as $(I-U_kU_k^T)(ER^{-1})$ (again, computing $ER^{-1}$ via triangular solves is only $\mathcal{O}(s^3)$ given the sparsity). Note that these all could be written with nnz(E), but again this is all only needed if nnz(E) is substantially less than $n.$ The method already implicitly assumes $U_k$ is stored as part of the process. In some sense this is what the manuscript proposes, but with what feels like an unnecessary amount of machinery that obscures the message. (Also, use of Cholesky would likely be faster since standard libraries could be used throughout). Moreover, given this simple interpretation it is not clear that Theorem 1 is particularly novel or interesting.

Related to the above points, the numerical experiments would be stronger if they were more clearly designed to show the tradeoffs between methods (e.g., using some synthetic examples where the sparsity can be controlled) rather than just "plausible" situations. The former actually seems more important since the accuracy should be the same. The key is to show when to use which method base on, e.g., the sparsity of $E.$ The numerical experiments are not illuminating in this regard.

While there is clearly effort in blending these ideas into prior work and building the numerical experiments (and therefore some contribution), ultimately the manuscript does not do a good job clearly articulating what this is. This is compounded by a lack of clarity in many places.

Assorted minor comments:

• Maybe it would be better to use different notation for the row, column, and low-rank updates to $A$ (i.e., not always using $E$). This can actually get confusing when thinking about dimensions of the appropriate projections.

• Equation (3) has a typo, it should be $U_kC.$

The paper has numerous grammatical mistakes and typos, for example in the title, abstract, and first paragraph of the intro:

• in the title what is "in sparse matrix"? The statement does not make sense, is it supposed to be "with sparse matrices"?

• abstract: "updating truncated singular value decomposition" -> "updating a truncated singular value decomposition"

• abstract: "Numerical experimental results on updating truncated SVD for evolving sparse matrices" -> Numerical experiments updating a truncated SVD for evolving sparse matrices

• abstract: "maintaining precision comparing" -> "maintaining precision comparable"

• intro P1: "Truncated Singular Value Decomposition (truncated SVD) is widely used in various machine..." -> "Truncated Singular Value Decompositions (SVDs) are widely used in various machine..."

• intro P1: "learning with truncated SVD benefits..." -> "learning with a truncated SVD benefits"

• intro P1: "interpretability provided by optimal Frobenius-norm" is not a cogent statement about the SVD; maybe what is meant is "interpretability because of its optimal approximation properties"? or similar?

• intro P1: "data under randomized" -> "data using randomized"

Accordingly, the manuscript would greatly benefit from a careful editing pass to address these issues (as they continue throughout the manuscript).

Update after author response

I would like to thank the authors for their thoughtful replies to my concerns and those of other reviewers.

While some of the responses do help highlight the scope of the contribution (e.g., in terms of how to think of nnz(E)), this is not really reflected in the manuscript. Saying “input sparsity” time is fine in places, but it is more useful to follow up and contextualize that statement in terms of the sparsity of the update. This does not really seem present in the updated manuscript.

Nevertheless, my overall opinion of the manuscript remains essentially unchanged (I have slightly updated my score, though the unallowable 4 would more accurately reflect my current opinion). There is a (somewhat narrow, but perhaps sufficient) contribution and it might be a good fit for certain applications. However, the presentation of the manuscript is still lacking and that significantly blunts any contribution. Numerous grammatical errors remain, Theorem 1 is still not sensibly stated (i.e., Definition 2 does not actually fix my concern and “approximate” is still ambiguously defined) to be a sound theoretical result, Section 3.1 could be more simply presented, and there remain aspects of the manuscript that are unclear (some of which are new additions). E.g., the paragraph above Alg 1 and 2 is not incorrect (i.e., it refers to the old version, Appendix E.2 doesn’t even say what the experiment is (updating rows, updating columns, updating weights, …), In Section 3.3 there is an incorrect algorithm reference, which makes Appendix F unclear (is the complexity of add columns or add rows analyzed), and more.

Lastly, on a technical note, while the use of MGS as suggested addresses one type of potential numerical issue (i.e., if $B$ lies close to the column space of $U_k$), it does not address potential issues encountered by the persistent decoupled storage of vectors in the sparse + low-dimensional subspace. This may or may not be problematic. Hence, while Cholesky QR is also often ill-advised, it is not clear it is worse in this setting (and given some of the condition numbers reported later likely fine for the simple tasks).