Efficient Differentiable Approximation of the Generalized Low-rank Regularization

We sincerely thank the reviewer for the detailed comments and constructed feedbacks!

Question 1: How to you compute the power of the matrix in (6) or (7) ?
Response 1: In Eq. (6) and (7), consecutive matrix powers of the form $M, M^2, …, M^p$ are required (typically $p=5$). We compute all these required matrix powers iteratively, i.e., $M_{i+1}=M_i M$ for $i=1,…,p-1$.

Question 2: How do you truncate the Taylor and Laguere series ?
Response 2: In our experiments, the series of Taylor and Laguerre expansions are truncated up to the 5th degree. We also tested with higher degrees, but no further improvements can be observed.

Question 3: I would find it useful to have the precise algorithm you use in practice to compute (6) with the different approximations and the different parameters.
Response 3: Thank you for the interest in our work! Our code will be made publicly accessible on github after anonymous review. In our implementation, we use Mathematica to compute the required coefficients in (6) and (7), which are then input to the python code. We refer the reviewer to article [1], which shows how to compute the coefficients in the Laguerre expansions. Our code calculates coefficients of the Taylor expansion and the Laguerre expansions in a similar way. Besides, the computation is rather efficient, talking only several seconds on a personal laptop.

Question 4: Have the authors considered efficient backward pass via implicit differentiation of the fixed-point iterations ?
Response 4: We thank the reviewer for the suggestion. Though currently our iterative approach for calculating fix-points is sufficient for practical applications, it is certainly an interesting idea to further improve its efficiency with implicit differentiation. We will leave this exploration as a future work.

Question 5: In the DNN application, it is not clear if the regularization is applied during or after training.
Response 5: Our regularization is applied during training by adding an additional loss term to the original loss function.

Question 6: Do you train a different model for each sigma parameter, or do you use sigma as a parameter of the model ?
Response 6: We trained a separate model for each noise level, following the previous experiment pipeline.

Question 7: Why the low-rank structure is only applicable to the entire image?
Response 7: The application of low-rank structure in image tasks is based on the observation that, most singular values of natural images are concentrated in a few of the largest ones [2]. This phenomenon becomes less evident when the patch becomes too small and the distribution deviates from that of natural images.

Question 8: For the denoising applications, which regularizer do you use?
Response 8: The results reported in the paper are obtained by using the basic nuclear norm regularization (i.e., Proposition 4). We also tested with other relaxation functions, but the difference is not evident in this particular task.

[1] MATHEMATICA TUTORIAL Part 2.5: Laguerre expansions (https://www.cfm.brown.edu/people/dobrush/am34/Mathematica/ch5/laguerre.html).

[2] Shang, F., Cheng, J., Liu, Y., Luo, Z. Q., & Lin, Z. (2017). Bilinear factor matrix norm minimization for robust PCA: Algorithms and applications. IEEE transactions on pattern analysis and machine intelligence, 40(9), 2066-2080.

We thank the reviewer for the interest and questions to our work.

Question 1: However, it lacks some essential details, such as specifying the objective function for different problems and explaining how their algorithm derives the corresponding regularization.
Response 1: We have presented and explained the objective function of each task at the end of the problem statement section (i.e., Section 3.1). We apologize for the unclarity, and will include a detailed discussion of the objective functions and the regularization terms in the experiment section.

Question 2: In section 4.1, there are five different variations of the author's algorithm compared to other methods, which raises questions about whether there is randomness in the application of a particular method for matrix completion .
Response 2: To address the concern about the randomness of our method’s performance, we conducted extensive experiments based on Table 1, the results are presented below. In the new experiments, each case is run for 10 times with random seeds, and we present the mean and standard deviation of the PSNR scores. Our method still consistently outperforms other baselines, and the standard deviations are also small, showing the stability of our method.

Question 3: Sections 4.2 and 4.3 also fall short by not providing comparisons with similar methods in the field.
Response 3: About video fore-background separation (Sections 4.2): The dataset used for this experiment is unannotated and without ground truth separation results. Consequently, related papers only presented qualitative results, and there is no numerical metrics can be compared with.

About DNN denoising (Sections 4.3): A key advantage of our method is that the low-rank regularization term can be conveniently applied to sophisticated DNN models, and we are unaware of any existing work has the same feature. Most previous methods are based on ADMM, and their experiments focus on basic matrix completion tasks without DNNs involved. At this moment, we can not identify a proper baseline for fair comparison on the DNN denoising problem.

We thank the reviewer for the interest and positive feedbacks on our work!

Question 1: It would have been nice to see some results on the approximation errors that one gets as one truncates the infinite sums in equations 6 and 7. This may help the user to choose the truncation point N.

Response 1: In our experiments, the series of Taylor and Laguerre expansions are truncated up to the 5th degree. We also tested with higher degrees, but no further improvements can be observed.

We thank the reviewer for the critical and constructive questions for our work.

Question 1: This paper introduces a smooth approximation technique for the rank function, which is a well-explored area in the literature, featuring numerous convex and nonconvex approximation methods. However, the paper lacks an optimality analysis of the proposed technique, leaving it unclear why this particular strategy is necessary.
Response 1: Though various convex and nonconvex application methods exist in the literature, our method possesses several unique advantages that distinguished from other works: 1) Our method can be generalized to various convex and nonconvex relaxations, while each previous work focuses on its particular form of low-rank regularization without a unified treatment. 2) Our method makes the low-rank regularization differentiable, which is compatible to modern deep learning models and libraries. 3) Our method is rather convenient to apply. The regularization term can be added in a plug-and-play fashion, and only a few lines of codes are needed to adapt to a new problem. 4) Our method is GPU-friendly and takes advantages of the efficient parallel computation, since the proposed method solely depends on matrix multiplication.

Though it remains a theoretical challenge for the optimality and convergence analysis of our method, our paper presents the first low-rank approximation technique that simultaneously possess the above characteristics. Besides, the superior effectiveness and efficiency of our method have been thoroughly demonstrated in the experiments.

Question 2: It is unclear whether the gradient descent algorithm will converge when another sub-iteration is introduced to estimate the matrix pseudo-inverse or matrix square root .
Response 2: We would like to address the reviewer’s concern on convergence with the following points:

1. The sub-iterations only involve several matrix multiplications/additions/subtractions, all of which are differentiable operations that permits gradient propagation. So there is no particular obstacle for gradient descent.
2. Similar iterative methods for computing matrix square root have been successfully applied in previous work, while no convergence issues have been observed [].
3. Empirically, our method can efficiently converge, as demonstrated in the experimental studies. Also a dedicated experiment about the convergence can be found in Appendix A.2.1.

Question 3: The authors suggest employing Laguerre expansion to handle the low-rank regularization function, with alpha_{k,p} representing the polynomial coefficients. The authors mention that these necessary coefficients can be computed using readily available tools like Mathematica; however, the complexity of computing these coefficients remains unclear. Furthermore, the paper does not discuss specific ranges for k and p .
Response 3: We apologize for the unclarity. Implementation details of the Laguerre expansion are presented as follows:

1. In Mathematica, the coefficients are computed by numerically integrating a 1d function, which is a very efficient procedure.
2. Particularly, it takes only several seconds to complete the computation on a personal laptop. Since the coefficients only need to be computed once, the overall computational overhead is negligible.
3. The Mathematica code of our implementation will be publicly available in our repository. We refer the reviewer to article [2], which is similar to our implementation.
4. In our experiments we set the ranges of k and p to be 5. In other words, the series of Taylor and Laguerre expansions are truncated up to the 5th degree. We also tested with higher degrees, but no further improvements can be observed.

[1] Lin, Tsung-Yu, and Subhransu Maji. "Improved Bilinear Pooling with CNNs." Proceedings of the British Machine Vision Conference, 2017.

[2] Li, Peihua, et al. "Towards faster training of global covariance pooling networks by iterative matrix square root normalization." Proceedings of the IEEE conference on computer vision and pattern recognition. 2018.

[3] MATHEMATICA TUTORIAL Part 2.5: Laguerre expansions (https://www.cfm.brown.edu/people/dobrush/am34/Mathematica/ch5/laguerre.html).

We hope our responses would address the reviewer’s concerns and clarify the misunderstandings. We also welcome the reviewer for any further questions and suggestions for our work.

Thanks for your hard work and valuable comments of this work. Here are responses for your concerns and questions:

Question 1: The authors should present the detailed algorithms as well as convergence analysis when using the proposed model for specific applications such as matrix completion as well as video foreground and background separation.
Response 1: We thank the reviewer for the suggestions. We will add a detailed algorithm description in the Appendix in the revised version. Rigorous theoretical convergence analysis is challenging in our case. Since our method novely applies several approximations for computing matrix root and inversion, existing analysis techniques cannot be directly applied. Nevertheless, our method converges quite well in practice. One representative example is the convergence result shown in Appendix A.2.1.

Question 2: Some important related works such as [1-5] should be discussed and compared in this work as they are representative works that are dealing with the same problem as the current work.
Response 2: Thank you for pointing out these important related works. In the table below we listed some key aspects of these researches and make comparisons with our work. Particularly, we would like to point out that:

1. Our method is based on a stochastic approximation of the low-rank regularization function, which to the best of our knowledge, is a completely novel approach compared with other related work.
2. Since our optimization method is gradient-based, it can be convenient applied to popular deep learning models and libraries. A discussion and comparison with these related works will be included in the revised manuscript.

Question 3: To my knowledge, the variational representation of the nuclear norm as well as the non-convex regularization do not need to know the exact rank, such as [1,2,4,5] .
Response 3: Though these methods do not need to know the exact rank, they need to know “the upper bound of the exact rank”: most factorization methods assume $A=BC$ where $A\in R^{m\times n}$, $B\in R^{m\times k}$, and $C\in R^{k\times n}$. Here the choice of $k$ requires strong prior knowledge, and many previous works show that an inappropriate choice will deteriorate the performance.

Question 4: The authors argue that the SVD is not differentiable, please refer to [6] for more information.
Response 4: We sincerely thank the reviewer for pointing out the result unknown to us before. Indeed, it presents a method for computing the gradients of SVD. The related discussions in our manuscript will be modified accordingly. However, though the result shows that differentiating SVD is possible, it is far from being practical. The prohibitive $O(N^4)$ complexity for computing gradients is unacceptable in our setting.

Question 5: (About running time) As for as I know, MSS is a representative factorization-based model which is much faster than the IRNN . (About performance gain) Where does the performance gain come from?
Response 5:

About running time: For all the compared baselines, we use the codes from public repositories and locally evaluated their performance with the same environment. Particularly, the code of MSS is taken from [6], and the code of IRNN is from [7]. The exact running times may vary between implementations.

About performance gain: There are two major reasons that explains the superior performance of our method:

1. Our method benefits from the non-convex relaxation of the rank function. Many of the compared baselines use the nuclear norm or Schatten-p quasi-norms with p<1, while our method utilizes more sophisticated relaxation.
2. Even the non-convex relaxation function and the mathematical models are the same, different methods have unequal convergence behaviors. We also note that while many related works have presented convergence analysis, these results typically characterize the worst-case performance, and may not fully explain the empirical performance.

[6] https://github.com/xuchen314/MSS/tree/master

[7] https://github.com/canyilu/Iteratively-Reweighted-Nuclear-Norm-Minimization