Dynamic matrix recovery from incomplete observations under an exact low-rank constraint

Abstract

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 {\em matrix sensing} and {\em 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.

References in corpus (5)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Guaranteed Matrix Completion via Non-convex Factorization
• A State-Space Approach to Dynamic Nonnegative Matrix Factorization

Cited by in corpus (7)

• Global Optimality in Low-rank Matrix Optimization
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Deep inference of latent dynamics with spatio-temporal super-resolution using selective backpropagation through time
• Recovery Guarantees for Time-varying Pairwise Comparison Matrices with Non-transitivity
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• Dynamic Matrix Recovery
• Online Variational Bayesian Subspace Filtering with Applications