4-应用案例-低秩矩阵恢复

知识点：低秩矩阵恢复

知识点概述

低秩矩阵恢复旨在从不完整的观测数据中恢复出一个完整的低秩矩阵。它在推荐系统、计算机视觉等领域有重要应用，其求解思路与稀疏优化类似，通过最小化核范数来实现。

教材原文

…寻找一个低秩矩阵 $X$ 可能给出很好的解。令 $\mathrm{rank}(X)$ 为矩阵 $X$ 的秩，该问题可以表达为

$$\underset{X\in {\mathbb{R}}^{m\times n}}{\min }\mathrm{rank}(X),\text{\hspace{1em}(1.3.1)}$$ $$\begin{array}{ll}\text{s . t .}& X_{ij}=M_{ij},(i,j)\in \Omega .\end{array}$$

…极小化矩阵的秩是 NP 难的问题…根据稀疏优化的思想, 我们将其更换成所有奇异值的和, 即矩阵 $X$ 的核范数 (nuclear norm): $\Vert X{\Vert }_{\ast }={\sum }_i{\sigma }_i(X)$ .

详细解释

• 背景: 在推荐系统（如Netflix电影推荐）等场景中，数据矩阵（用户-物品评分矩阵）通常是不完整的，但我们假设其内在结构是简单的，即矩阵是低秩的。
• 核心问题 (Rank Minimization): 直接最小化矩阵的秩是NP难问题，类似于${\ell }_0$范数最小化。
• 凸松弛 (Nuclear Norm Minimization): 矩阵的秩是其非零奇异值的个数。类比于${\ell }_1$范数是向量元素绝对值之和，核范数是矩阵奇异值之和。最小化核范数是秩最小化问题的一个凸代理，可以高效求解。
• 与稀疏优化的关系: 低秩矩阵恢复可以看作是稀疏优化在矩阵奇异值向量上的推广。

学习要点

• 理解“低秩”对于矩阵数据的意义（如数据冗余、存在潜在简单结构）。
• 了解秩最小化是NP难问题。
• 掌握核范数的定义（奇异值之和）及其作为秩函数的凸代理的核心思想。

实践应用

• 推荐系统: 预测用户对未评分物品的评分（矩阵补全）。
• 计算机视觉: 从损坏或有遮挡的图像中恢复背景（鲁棒PCA）。
• 系统辨识: 从输入输出数据中确定线性时不变系统的阶数。

关联知识点

• 前置知识: 3-应用案例-稀疏优化, 15-核心概念-矩阵范数
• 后续知识: 46-核心概念-矩阵优化, 45-核心概念-半定规划
• 相关知识: 35-应用案例-主成分分析