Dynamic matrix recovery from incomplete observations under an exact low-rank constraint
Low-rank matrix factorizations arise in a wide variety of applications -including recommendation systems, topic models, and source separation, to name just a few. In these and many other applications, it has been widely noted that by incorporating temporal information and allowing for the possibility of time-varying models, significant improvements are possible in practice. However, despite the reported superior empirical performance of these dynamic models over their static counterparts, there is limited theoretical justification for introducing these more complex models. In this paper we aim to address this gap by studying the problem of recovering a dynamically evolving low-rank matrix from incomplete observations. First, we propose the locally weighted matrix smoothing (LOWEMS) framework as one possible approach to dynamic matrix recovery. We then establish error bounds for LOWEMS in both the matrix sensing and matrix completion observation models. Our results quantify the potential benefits of exploiting dynamic constraints both in terms of recovery accuracy and sample complexity. To illustrate these benefits we provide both synthetic and real-world experimental results.
The authors analyze low rank matrix estimation in a simple dynamic setting where one of the low rank factors varies smoothly across time intervals. This a first attempt at theoretical understanding of dynamic models in high dimensional matrix estimation. The authors derive consistent error bounds for the proposed dynamic model using a weighted squared error minimizer under a non-convex rank constraint.
My primary concerns are listed below: A. Proof 1. a) In line 379 (supplementary material) Theorem 2.3 from 5 cannot be directly used to establish RIP for \sum_t \sqrt{wt} At(\Delta)  as \sum_t wt ||At(\Delta)||_2^2  NOT = ||\sum_t \sqrt{wt} At(\Delta)||_2^2. However, as theorem 3.1 requires bound on only the former, the proof in [5] can be extended. The proof needs some work though. b) Lemma B.2 inequality is reversed.   B. Theory 2. The results are derived for exact global solution to (2) which is a non-convex optimization. The paper is incomplete without the suggested future work on analyzing alternating minimization. I believe the analysis will follow through with a bit of linear algebra machinery, but the exact expression of the joint error term arising from Thm 3.4 and 3.8 and the weighted power iteration is more useful towards understanding the tradeoff of sample complexity and accuracy using the dynamic estimation in practical implementations.  3. For the proposed estimator, simple extensions to the dynamic model analyzed (in line 108) can drastically increase the number of parameters to be estimated using cross validation as explained below: a) Since the e^t are all assumed to be Gaussian with mean zero and a common standard deviation of sigma_2 (independent of t). This setting essentially boils down to the standard matrix estimation problem, where the samples have different noise levels, i.e. each y^t as samples from X^d with Gaussian noise of sigma_1+\|U\|(d-t)sigma_2. b) At a high level, the optimum w^t essentially would weight the fit to the samples based on the noise level at y^t.The algorithm for computing optimum w^t requires estimating a  \kappa parameter (which depends on sigma_1,sigma_2) using cross validation. c) Even for a simple extension of having different sigma_t for e^t, the optimum estimation of w^t would require essentially estimating all the different noise variances using cross validation which can be computationally demanding. d) As I understand, in a naive implementation the optimum w^t require knowledge of noise level of y^t (which is restrictive). A different estimator to avoid this dependence on noise variant might be more useful here. The following work might be relevant in this regard: Klopp, Olga, and Stéphane Gaiffas. "High dimensional matrix estimation with unknown variance of the noise." (2015).  C. Experiments: What does it mean to get results at a particular \kappa? The following comments assume that the authors solve for w^t using the QP in eq 5 using \kappa=\kappa in plots. 4. Figure 1: a) I am not able to judge the significance of the differences from baseline in both experiments. Since the authors have already run the experiments 5 times, I suggest they add error bars to the Figure 1. b) Optimum \kappa for Fig 1a does not match the theoretical values for matrix sensing even for data simulated from modeling assumptions. c) It is very difficult to understand this figure and the corresponding text. The key point I think is that the optimum \kappa for min recovery error increases as sigma 1 increases. This can be highlighted by using labels to indicate the optimum \kappa as (LOWEMS), \kappa\sim1e-2 as baseline 2 and \kappa > 10e2 as baseline 1.  5. Figure 3a: Since both gamma and kappa are chosen from cross validation. The result does not necessarily indicate that the performance improvement is from choosing kappa optimally. I suggest controlling for changes in gamma in this experiment.  (suggestion) 6. Figure 2 highlights the trade-off between sample complexity and accuracy achieved by LOWEMS. However, I think a better plot to illustrate the effect would be to plot two figures (a) for each model m plot the sigma 2 vs the # of samples to for error convergence (say # samples so that the error is below 1.1*min_error(m) ), and (b) for each model m plot the sigma 2 vs the #min_error(m)   MINOR: Line 24: "most popular approach in recent years has focused on the use of nuclear norm minimization as a convex surrogate": This is true for theoretical analysis. The low rank constraint and alternating minimization are more popular in practice. Line 50: use Big O notation or state that C^i are constants. Line 108: equation number Thm 3.4: State that D_1 is also a constant and \delta_1,\delta_2r are RIP constants from Def 3.3 not any positive constants  [EDIT]: I have read the author response and my review remains unchanged. In summary, there are some interesting ideas and potential reference value in being the first analysis of theoretical properties of a dynamic matrix completion model. However, the model analyzed is too simplistic, and the significance of the paper is further undermined by the lack of analysis for a working algorithm (like alternating minimization).  I am currently unable to judge the significance of empirical improvements without the error bars (although the authors response claims to include them).