核范数为什么能够作为矩阵秩的凸替换 、 核范数如何应用到张量中从而进行张量秩的约束_张量的核范数

• 对于经典的低秩矩阵补全优化问题:
  $$\begin{array}{r}\underset{X}{\min }:rank(X)\\ s.t.:X_{\Omega }=M_{\Omega }\end{array}\text{\hspace{1em}(1)}$$
  $(1)$ 中的优化问题是非凸的,因为 $rank(X)$ 是非凸函数
  • 一种常见的方法是采用核范数来近似矩阵的秩，核范数被证明是在一定意义下，rank的最佳凸估计/凸松弛[1]
  • 进而可以将 $(1)$ 中的问题转变成以下的矩阵补全的凸优化问题:
    $$\begin{array}{r}\underset{X}{\min }:\Vert X{\Vert }_{\ast }\\ s.t.:X_{\Omega }=M_{\Omega }\end{array}\text{\hspace{1em}(2)}$$
  • 张量是矩阵概念的推广。通过求解以下优化问题，可以将矩阵情况下的补全算法推广到高阶张量：
    $$\begin{array}{r}\underset{\mathcal{X}}{\min }:\Vert \mathcal{X}{\Vert }_{\ast }\\ s.t.:{\mathcal{X}}_{\Omega }={\mathcal{T}}_{\Omega }\end{array}\text{\hspace{1em}(3)}$$
  • 第一个问题是一般张量情况下的核范数的定义。[2]提出了以下关于张量迹范数的定义：
    $$\begin{array}{r}\underset{\mathcal{X}}{\min }:\sum _{i=1}^n{\alpha }_i\Vert {\mathcal{X}}_{(i)}{\Vert }_{\ast }\\ s.t.:{\mathcal{X}}_{\Omega }={\mathcal{T}}_{\Omega }\end{array}\text{\hspace{1em}(4)}$$
  • 这里有人可能会问，为什么不把张量核范数定义为张量秩的凸包络。与矩阵不同，计算一般张量（阶数> 2）的秩是一个NP困难问题[3]。此外，据所知[2]，张量秩的凸包络并没有显式的表达式。

2、a simple low rank tensor completion algorithm(SiLRTC)

• $(4)$ 中的问题由于不同矩阵核范数项相互依赖而难以解决，即当优化多个矩阵核范数的和时，矩阵共享相同的元素，不能够独立优化。所以需要首先分离变量，然后再独立的进行求解。因此引入 $M_1,...,M_n$,然后将 $(4)$ 转换成如下方案:
  $$\begin{array}{rl}& \underset{\mathcal{X}}{\min }:\sum _{i=1}^n{\alpha }_i\Vert M_{(i)}{\Vert }_{\ast }\\ & s.t.:{\mathcal{X}}_{(i)}=M_{i}fori=1,...,n\\ & {\mathcal{X}}_{\Omega }={\mathcal{T}}_{\Omega }.\end{array}\text{\hspace{1em}(5)}$$
• 在上述方案中,核范数仍然不是独立的,因为 $M_i={\mathcal{X}}_{(i)}$ ，导致矩阵 $M_i$ 共享相同的元素。可以放宽等式约束，即用 $\Vert M_i-{\mathcal{X}}_{(i)}{\Vert }_F^2<d_i$ 替换 ${\mathcal{X}}_{(i)}=M_i$ :
  $$\begin{array}{rl}& \underset{\mathcal{X}}{\min }:\sum _{i=1}^n{\alpha }_i\Vert M_{(i)}{\Vert }_{\ast }\\ & s.t.:\Vert M_i-{\mathcal{X}}_{(i)}{\Vert }_F^2<d_{i}fori=1,...,n\\ & {\mathcal{X}}_{\Omega }={\mathcal{T}}_{\Omega }.\end{array}\text{\hspace{1em}(6)}$$
  $d_i$ 是一个可以由用户定义的阈值，进一步可以将不等式约束转换成等式约束。
  $$\begin{array}{rl}& \underset{\mathcal{X}}{\min }:\sum _{i=1}^n{\alpha }_i\Vert M_{(i)}{\Vert }_{\ast }+\frac{{\beta }_i}{2}\Vert M_i-{\mathcal{X}}_{(i)}{\Vert }_F^2\\ & s.t.{\mathcal{X}}_{\Omega }={\mathcal{T}}_{\Omega }.\end{array}\text{\hspace{1em}(7)}$$
  这是一个凸但不可微的优化问题。
• 对于上述问题采用块坐标下降法进行优化(块坐标下降的基本思想是在固定其他组变量时，进而优化剩余变量组)，将 $(4)$ 中的变量分为 $\mathcal{X},M_1,M_2,\cdots ,M_n$ .
  • 计算 $\mathcal{X}$:当固定其他变量时，即需要解决以下问题:
    $$\begin{array}{rl}& \underset{\mathcal{X}}{\min }:\sum _{i=1}^n\frac{{\beta }_i}{2}\Vert M_i-{\mathcal{X}}_{(i)}{\Vert }_F^2\\ & s.t.:{\mathcal{X}}_{\Omega }={\mathcal{T}}_{\Omega }.\end{array}\text{\hspace{1em}(8)}$$
    $(7)$ 问题求解结果为:
    $${\mathcal{X}}_{i_1,\dots ,i_n}=\{\begin{array}{ll}(\frac{{\sum }_i{\beta }_{i}fol{d}_i(M_i)}{{\sum }_i{\beta }_i}{)}_{i_1,\cdots ,i_n}& (i_1,\cdots ,i_n)\notin \Omega \\ {\mathcal{T}}_{i_1,\cdots ,i_n}& (i_1,\cdots ,i_n)\in \Omega \end{array}$$
  • 计算 $M_i$ .$M_i$ 是以下形式的最优解:
    $$\begin{array}{rl}\underset{M_i}{\min }& :\frac{{\beta }_i}{2}\Vert M_i-{\mathcal{X}}_{(i)}{\Vert }_F^2+{\alpha }_i\Vert M_i{\Vert }_{\ast }\\ & \equiv \frac{1}{2}\Vert M_i-{\mathcal{X}}_{(i)}{\Vert }_F^2+\frac{{\alpha }_i}{{\beta }_i}\Vert M_i{\Vert }_{\ast }\end{array}\text{\hspace{1em}(9)}$$
    $(8)$ 问题的最优解 $M_i$ 可以直接通过计算 $D_{\tau }({\mathcal{X}}_{(i)})$ ,其中 $\tau =\frac{{\alpha }_i}{{\beta }_i}(SVT:奇异值阈值算法)[4]$

3、a high accuracy low rank tensor completion algorithm(HaLRTC)

采用 $\text{ADMM}$ 算法，基于 $\text{SiLRTC}$ 算法，并在此基础上给出了一个使用 $\text{ADMM}$ 框架的简单实现。在算法 $\text{SiLRTC}$ 中引入了$M_1,...,M_n$ ，是作为 ${\mathcal{X}}_{(i)}$ 的替代。此处仍采用这种方式，但是采用的是 ${\mathcal{M}}_i$ 代替 $\mathcal{X}$.目标函数如下:
min ⁡ X , M 1 , ⋯   , M n : ∑ i = 1 n α i ∥ M i ( i ) ∥ ∗ s . t . : X Ω = T Ω X = M i ,   i = 1 , … , n . (10)

$$\begin{aligned} \min_{\mathcal{X,M_1,\cdots,M_n}} &:\sum_{i=1}^{n} \alpha_i \|\mathcal{M}_{i(i)} \|_* \\ s.t. &:\mathcal{X_{\Omega}=T_{\Omega}} \\ & \mathcal{X}=\mathcal{M_i},~ i=1,\dots,n. \end{aligned}$$ \tag{10} X,M1​,⋯,Mn​min​s.t.​:i=1∑n​αi​∥Mi(i)​∥∗​:XΩ​=TΩ​X=Mi​, i=1,…,n.​(10)

• 将增广拉格朗日函数定义如下：
  $$\begin{array}{rl}& L_{\rho }(\mathcal{X},{\mathcal{M}}_1,\dots ,{\mathcal{M}}_n,{\mathcal{Y}}_1,\dots ,{\mathcal{Y}}_n)\\ & =\sum _{i=1}^n{\alpha }_i\Vert {\mathcal{M}}_{i(i)}{\Vert }_{\ast }+<\mathcal{X}-{\mathcal{M}}_i,{\mathcal{Y}}_i>+\frac{\rho }{2}\Vert {\mathcal{M}}_i-\mathcal{X}{\Vert }_F^2\end{array}\text{\hspace{1em}(11)}$$
• 计算 ${\mathcal{M}}_i,\mathcal{X},{\mathcal{Y}}_i$ 分别求解下列三个函数即可:
  • { M 1 k + 1 , … , M 1 k + 1 } = arg min ⁡ M 1 , … , M n : L ρ ( X k , M 1 , … , M n , Y 1 k + 1 , … , Y n k + 1 ) \{\mathcal{M}_1^{k+1},\dots,\mathcal{M}_1^{k+1}\} =\argmin_{\mathcal{M_1},\dots,\mathcal{M_n}}: L_{\rho}(\mathcal{X^k,M_1,\dots,M_n,Y_1^{k+1},\dots,Y_n^{k+1}}) {M1k+1​,…,M1k+1​}=argminM1​,…,Mn​​:Lρ​(Xk,M1​,…,Mn​,Y1k+1​,…,Ynk+1​)
  • ${\mathcal{X}}^{k+1}={\mathrm{argmin}}_{\mathcal{X}\in Q}:L_{\rho }(\mathcal{X},{\mathcal{M}}_1^{k+1},\dots ,{\mathcal{M}}_n^{k+1},{\mathcal{Y}}_1^{k+1},\dots ,{\mathcal{Y}}_n^{k+1})$
  • ${\mathcal{Y}}_i^{k+1}={\mathcal{Y}}_i^k-\rho ({\mathcal{M}}_i^{k+1}-{\mathcal{X}}^{k+1})$
  • 更新 ${\mathcal{M}}_i$ :
    可以写出 ${\mathcal{M}}_i$ 的目标函数 $f({\mathcal{M}}_i)={\alpha }_i\Vert {\mathcal{M}}_{i(i)}{\Vert }_{\ast }+<\mathcal{X}-{\mathcal{M}}_i,{\mathcal{Y}}_i>+\frac{\rho }{2}\Vert {\mathcal{M}}_i-\mathcal{X}{\Vert }_F^2$
    对上述目标函数进行求导 $({\alpha }_i\Vert {\mathcal{M}}_{i(i)}{\Vert }_{\ast }{)}^{{}^{\prime }}-{\mathcal{Y}}_i+\rho ({\mathcal{M}}_i-\mathcal{X})$
    然后对上述导数求积分形式为:$f({\mathcal{M}}_i)={\alpha }_i\Vert {\mathcal{M}}_{i(i)}{\Vert }_{\ast }+\frac{\rho }{2}\Vert {\mathcal{M}}_i-\mathcal{X}-\frac{1}{\rho }{\mathcal{Y}}_i{\Vert }_F^2+C_{M_i}$
    上述目标函数可以采用 $\text{SVT}$ 进行求解，结果为:
    ${\mathcal{M}}_i=fol{d}_i[D_{\frac{{\alpha }_i}{\rho }}({\mathcal{X}}_{(i)}+\frac{1}{\rho }{\mathcal{Y}}_{i(i)})]$
  • 更新 $\mathcal{X}$:
    可以写出 $\mathcal{X}$ 的目标函 $f(\mathcal{X})={\sum }_{i=1}^n{\alpha }_i\Vert {\mathcal{M}}_{i(i)}{\Vert }_{\ast }+<\mathcal{X}-{\mathcal{M}}_i,{\mathcal{Y}}_i>+\frac{\rho }{2}\Vert {\mathcal{M}}_i-\mathcal{X}{\Vert }_F^2$
    对上述目标函数进行求导:${\sum }_{i=1}^n{\mathcal{Y}}_i+\rho (\mathcal{X}-{\mathcal{M}}_i)$
    令其等于零即可:${\mathcal{X}}_{\Omega }=\frac{1}{n}({\sum }_{i=1}^n{\mathcal{M}}_i-\frac{1}{\rho }{\mathcal{Y}}_i)$
  • 更新 ${\mathcal{Y}}_i$: ${\mathcal{Y}}_i={\mathcal{Y}}_i-\rho ({\mathcal{M}}_i-\mathcal{X})$

参考文献

• [1] Recht B, Fazel M, Parrilo P A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J]. SIAM review, 2010, 52(3): 471-501.
• [2] Liu J, Musialski P, Wonka P, et al. Tensor completion for estimating missing values in visual data[J]. IEEE transactions on pattern analysis and machine intelligence, 2012, 35(1): 208-220.
• [3] Hillar C J, Lim L H. Most tensor problems are NP-hard[J]. Journal of the ACM (JACM), 2013, 60(6): 1-39.
• [4] Cai J F, Candès E J, Shen Z. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on optimization, 2010, 20(4): 1956-1982.