Dynamic Matrix Recovery

Matrix recovery from sparse observations is an extensively studied topic emerging in various applications, such as recommendation system and signal processing, which includes the matrix completion and compressed sensing models as special cases. In this work, we propose a general framework for dynamic matrix recovery of low-rank matrices that evolve smoothly over time. We start from the setting that the observations are independent across time, then extend to the setting that both the design matrix and noise possess certain temporal correlation via modified concentration inequalities. By pooling neighboring observations, we obtain sharp estimation error bounds of both settings, showing the influence of the underlying smoothness, the dependence and effective samples. We propose a dynamic fast iterative shrinkage-thresholding algorithm that is computationally efficient, and characterize the interplay between algorithmic and statistical convergence. Simulated and real data examples are provided to support such findings.基于稀疏观测的矩阵恢复是一个被广泛研究的课题，其在推荐系统（recommendation system）与信号处理等诸多应用领域中均有应用，矩阵补全与压缩感知（compressed sensing）模型均为其特例。本研究针对随时间平滑演化的低秩矩阵动态恢复问题，提出了一种通用分析框架。我们首先假设观测在时间维度上相互独立，随后通过改进的集中不等式（concentration inequalities），将研究推广至设计矩阵与噪声均存在一定时间相关性的场景。通过聚合邻域观测，我们推导得到了两类场景下的精确估计误差界，阐明了底层平滑性、相关性与有效样本量对恢复性能的影响。我们提出了一种计算高效的动态快速迭代收缩阈值算法（dynamic fast iterative shrinkage-thresholding algorithm），并刻画了算法收敛与统计收敛之间的内在关联。本文通过仿真与真实数据集实验验证了上述研究结论的有效性。