基于可逆线性变换的低秩张量补全与张量核范数

minX ∥X∥∗, s.t. PΩ(X) = PΩ(M),(1)159960基于可逆线性变换的低秩张量补全与张量核范数0卢灿毅 1 ，彭曦 2 ，魏云超 3 ，401 卡内基梅隆大学，2 四川大学，3 伊利诺伊大学香槟分校，4 悉尼科技大学0canyilu@gmail.com，pengx.gm@gmail.com，wychao1987@gmail.com0摘要0本文研究了低秩张量补全问题，旨在从部分观测条目中精确恢复低秩张量。我们的模型受到最近提出的基于可逆线性变换的张量张量积（t-product）[ 9 ]的启发。当线性变换满足一定条件时，我们推导出新的张量管秩、张量谱范数和张量核范数。借助张量核范数，我们通过求解凸规划来解决张量补全问题，并在某些张量不相干条件下提供了精确恢复的理论界限。所达到的采样复杂度是按顺序最优的。我们的模型和结果极大地扩展了低秩矩阵 [ 5 ]和张量补全 [ 16 ]的现有结果。数值实验验证了我们的结果，图像恢复应用证明了我们方法的优越性。01. 引言0随着廉价存储器的可用性和现代计算机技术的进步，科学和工程应用中的数据量比以往任何时候都要大。真实数据通常具有多维结构：信息存储在多维数组中，称为张量 [ 26]，其条目由几个连续或离散变量索引。例如，彩色图像是一个具有列、行和颜色模式的三维对象；灰度视频由两个空间变量和一个时间变量索引。许多涉及张量表示和操作的应用，包括信号处理 [ 6 ]，计算机视觉 [ 27 ]，数据挖掘 [ 23 ]等。在这些应用中的常见方法是通过利用其多维结构来操作张量数据。将多维数据折叠成矩阵通常会导致信息丢失并导致性能下降。观察到真实张量数据通常是极端低维的0然而，所关注的张量通常是低秩的，或者近似低秩的 [ 11]，因此具有较低维度的结构。这激发了低秩张量估计和恢复问题，在许多不同领域引起了重要关注，无论是在理论上还是在实践中：例如，估计潜在变量图模型 [ 1 ]，分类音频 [20 ]，图像和视频补全 [ 13 ,  16]，等等。在本文中，我们专注于低秩张量补全问题，旨在从不完整的观测中精确恢复低秩张量。这样的问题可以看作是低秩矩阵补全问题 [ 3 ,  5 ] 的扩展，已经应用于图像去噪 [18 ] 和多标签图像分类 [ 2]。研究表明，在某些不相干条件下，具有 O ( nr  log 2 n )观测的秩为 r 的矩阵 M ∈ R n × n可以通过求解以下凸模型 [ 5 ] 来以高概率恢复0其中，P Ω ( X ) 表示 X 在观测集合 Ω 上的投影，∥ X ∥ � 是X的核范数，定义为其奇异值之和。核范数是矩阵秩在某个集合内的凸包。与秩为 r 的矩阵的自由度 O ( nr ) 相比，( 1 )的采样复杂度 O ( nr  log 2 n ) 是按顺序最优的 [ 5]。预计将低秩矩阵补全模型和分析扩展到张量情况。已经提出了几种基于不同张量秩定义和凸代理的张量恢复模型。但是它们在实际应用中存在一些限制。CP秩 [ 11 ]定义为最小的秩一张量分解的数量，计算NP难。它的凸包不明确。这使得低CP秩张量恢复具有挑战性。为了避免这个问题，可处理的Tucker秩 [ 11 ]及其凸松弛更广泛使用。核范数之和（SNN）[ 13 ]用作凸代理minXk�i=1λi∥X{i}∥∗, s.t. PΩ(X) = PΩ(M),(2)590并应用于低秩张量补全（LRTC）[21]0其中 X { i } 是  X  的第 i 个模式矩阵化[11]， P Ω ( X ) 表示 X  在观测集合  Ω 上的投影，λ i  >  0。这种方法在图像处理中的有效性已经在[13, 7, 25,24]中得到了充分研究。然而，SNN并不是Tucker秩[22]的最紧凸松弛。从理论上讲，上述模型可能相对次优[21]，因为所需的测量次数远高于具有Tucker秩 ( r, r,  ∙ ∙ ∙  , r )的张量的自由度。这与使用核范数最小化的低秩矩阵补全模型拥有最优恢复速率[5]不同。最近，基于张量-张量乘积（t-乘积）和张量奇异值分解（t-SVD）[10]，提出了一种新的张量核范数，并应用于张量补全[16]和张量鲁棒PCA[14,15]。基于t-乘积诱导的张量核范数模型的主要优势在于它们具有与矩阵情况相同的紧密恢复界限[16]。在[9]中，作者观察到t-乘积基于一种类似卷积的操作，可以使用离散傅里叶变换（DFT）来实现。为了适当地推动这种基于变换的方法，提出了一种基于任意可逆线性变换的更一般的张量-张量乘积定义。基于变换的t-乘积还具有基于矩阵代数的解释，类似于[8]。这种基于变换的新t-乘积在实践中非常有趣，因为它允许对不同的以张量格式化的真实数据使用不同的线性变换。在这项工作中，我们专注于基于变换诱导的t-乘积的重要低秩张量恢复问题。具体而言，我们对以下问题感兴趣：0•如何通过基于线性变换的张量积定义新的张量秩和张量核范数？0• 对可逆线性变换的选择是否有限制？0•基于新的线性变换的张量核范数，是否存在相应的低秩张量补全的恢复保证？0本文的主要贡献是解决上述问题。我们证明如果线性变换满足一定条件，则可以通过基于变换的t-乘积定义一种新的张量核范数。我们可以进一步基于t-SVD定义与[10]中相同的张量管秩。最后，我们通过基于变换的张量核范数最小化来研究低管秩张量恢复问题，该问题是凸的。从理论上讲，我们0证明在某些张量不一致条件下，可以通过凸优化以高概率精确恢复底层低管秩张量。我们的模型和结果比[16]更加通用，因为我们有更多选择的可逆线性变换。我们主要结果的证明更具挑战性，因为基于变换的张量积在原始域中没有等效的表达式。这与基于原始域中的块循环矩阵结构定义的张量积[10]非常不同。这种结构在现有工作中的证明中非常重要，例如[16]。本文的其余部分结构如下。第2节0给出一些符号，并提出了基于变换的t-乘积诱导的新张量核范数。第3节通过最小化提出的张量核范数来解决低秩张量补全问题，并在理论上提供了精确的恢复保证。第4节介绍了在合成数据和实际数据上进行的数值实验。最后，我们在第5节总结了本文。02. 基于变换的新张量核范数0本节中，我们介绍本文中使用的一些符号和定义。其中一些来自于[10, 15]。02.1. 符号说明0我们用小写字母表示标量，例如  a，用粗体小写字母表示向量，例如  a，用粗体大写字母表示矩阵，例如  A，用粗体欧拉手写字母表示张量，例如  A。对于一个三维张量  A  ∈  R n 1 × n 2 × n 3，我们将其第 ( i, j, k ) 个元素表示为  A ijk  或  a ijk，并使用Matlab的表示法  A ( i,  : ,  :) ，  A (: , i,  :)  和  A (:,  : , i )  分别表示第 i 个水平切片、第 i 个侧面切片和第 i个前面切片[11]。更常见的是，前面切片  A (: ,  : , i )被简洁地表示为  A ( i ) 。管状体被表示为  A ( i, j,  :) 。在R n 1 × n 2 中，矩阵  A  和  B  的内积定义为  � A ,  B �  =Tr ( A � B ) ，其中  A � 表示  A  的转置，  Tr ( ∙ )表示矩阵的迹。在  R n 1 × n 2 × n 3 中，矩阵  A  和  B的内积定义为  � A ,  B �  = � n 3 i =1 � A ( i ) ,  B ( i ) �。我们用  I n  表示大小为 n × n0ijk | a ijk | ，无穷范数表示为  ∥ A ∥ ∞  = max ijk  | a ijk |，Frobenius范数表示为0作为  ∥ A ∥ F  = �� ijk a 2 ijk，分别。上述范数在矢量或矩阵时退化为矢量或矩阵范数。0i v 2 i . 矩阵  A  的谱范数表示为  ∥ A ∥  = max i  σ i ( A )，其中  σ i ( A ) 为矩阵  A  的奇异值。矩阵核范数定义为∥ A ∥ �  = �0i σ i ( A ) 。bcirc(A) =A(1)A(n3)· · ·A(2)A(2)A(1)· · ·A(3)............A(n3)A(n3−1)· · ·A(1) .unfold(A) =A(1)A(2)...A(n3) , fold(unfold(A)) = A,C = A ∗ B = fold(bcirc(A) · unfold(B)).(3)(F n3 ⊗ In1) · bcirc(A) · (F −1n3 ⊗ In2) = ¯A,(4)D = A ⊙ B(5)D(i) = A(i)B(i), i = 1, · · · , n3.(6)599802.2. 基于变换的张量核范数0工作[10]给出了张量张量乘积的第一个定义。对于  A  ∈  Rn 1 × n 2 × n 3 ，我们将  A  的块循环矩阵  bcirc ( A )定义为0我们还需要以下两个运算符0其中  unfold  运算符将  A  映射为大小为 n 1 n 3  ×  n 2的矩阵，  fold  是其逆运算符。设  A  ∈ R n 1 × n 2 × n3 ，  B  ∈  R n 2 × l × n 3 ，则张量乘积  C  = A  �  B定义为大小为  n 1  ×  l  ×  n 3  的张量，0块循环矩阵可以使用离散傅里叶变换（DFT）矩阵  F  n 3进行块对角化，即0其中  �  表示克罗内克积，  ¯ A  是一个块对角矩阵，第 i个块  ¯ A ( i )  是通过沿第3个维度对  A  进行DFT得到的  ¯A  的第 i 个前面切片，即  ¯ A  =  fft ( A ,  [ ] ,  3)，使用Matlab命令  fft 。我们用0表示前面切片逐元素相乘（[9]中的定义2.1），即0然后（ 4 ）中的块对角化性质意味着  ¯ C  = ¯ A  ⊙ ¯ B。因此，（ 3）中的张量乘积等价于在变换域中使用DFT进行矩阵乘积。在[9]中，作者提出了基于任意可逆线性变换  L的更一般的张量乘积定义。在本工作中，我们考虑线性变换L  ：  R n 1 × n 2 × n 3 → R n 1 × n 2 × n 3，它通过对每个管状体纤维  A ( i, j,  :)  应用变换来给出  ¯ A。或者我们有0¯A = L(A) = A ×3 L，(7)0算法1 基于变换L的t-乘积[9]0输入：A∈Rn1×n2×n3，B∈Rn2×l×n3，L：Rn1×n2×n3→Rn1×n2×n3。输出：C = A�LB∈Rn1×l×n3。01. 计算¯A = L(A)和¯B = L(B)。02. 通过以下方法计算¯C的每个前视面：0¯C(i) = ¯A(i)¯B(i)，i=1，∙∙∙，n303. 计算C = L^(-1)(¯C)。0其中×3表示第3模乘积（[9]中的定义2.5），L∈Rn3×n3可以是任意可逆矩阵1。类似地，我们有逆映射：0L^(-1)(A) = A ×3 L^(-1)。(8)0然后，基于L的t-乘积定义如下。0定义2.1.（t-乘积）[9]设L是(7)中的任意可逆线性变换，A∈Rn1×n2×n3，B∈Rn2×l×n3。则基于L的t-乘积记为C = A�LB，定义如下：L(C)= L(A)⊙L(B)。0我们将¯A∈Rn1n3×n2n3表示为一个块对角矩阵，其对角线上的第i个块是¯A的第i个前视面¯A(i)，即：0¯A = bdiag(¯A) =0�0�0¯A(1) ¯A(2)0... ¯A(n3)0�0����，0其中bdiag是一个将张量¯A映射为块对角矩阵¯A的运算符。因此，L(C) = L(A)⊙L(B)等价于¯C =¯A¯B。这意味着基于L的t-乘积等价于变换域中的矩阵乘积。算法1给出了计算t-乘积的方法。t-乘积具有许多类似于矩阵乘积的性质。例如，t-乘积是可结合的，即A�L(B�LC) =(A�LB)�LC。0定义2.2.（张量转置）[9]设L是(7)中的任意可逆线性变换，A∈Rn1×n2×n3。则张量转置记为A�，满足L(A�)(i)=(L(A)(i))�，i=1，∙∙∙，n3。0定义2.3.（单位张量）[9]设L是(7)中的任意可逆线性变换。令I∈Rn×n×n3，使得L(I)=¯I的每个前视面都是一个n×n大小的单位矩阵。则称I =L^(-1)(¯I)为单位张量。01 为了讨论的方便，我们将L限制为实矩阵。但是，如果需要，我们的结果仍然适用于复杂的L[9]。Theorem 2.1. (T-SVD) [9] Let L be any invertible lineartransform in (7), and A ∈ Rn1×n2×n3. Then it can befactorized asA = U ∗L S ∗L V⊤,(9)where U ∈ Rn1×n1×n3, V ∈ Rn2×n2×n3 are orthogonal,and S ∈ Rn1×n2×n3 is an f-diagonal tensor.Figure 1 gives an intuitive illustration of the t-SVD fac-torization. Also, t-SVD can be computed by performingmatrix SVD in the transform domain. See Algorithm 2.For any invertible linear transform L, we have L(0) =L−1(0) = 0. So both S and ¯S are f-diagonal tensors. Wecan use their number of nonzero singular tubes to define thetensor tubal rank as in [15].Definition 2.6. (Tensor tubal rank) Let L be any invertiblelinear transform in (7). For A ∈ Rn1×n2×n3, the tensortubal rank, denoted as rankt(A), is defined as the numberof nonzero singular tubes of S, where S is from the t-SVDof A = U ∗L S ∗L V⊤. We can writerankt(A) =#{i, S(i, i, :) ̸= 0}.For A ∈ Rn1×n2×n3 with tubal rank r, we also havethe skinny t-SVD, i.e., A = U ∗L S ∗L V⊤, where U ∈Rn1×r×n3, S ∈ Rr×r×n3, and V ∈ Rn2×r×n3, in whichU⊤∗LU = I and V⊤∗LV = I. We use the skinny t-SVDthroughout this paper. The tensor tubal rank is nonconvex.In Section 3, we will study the low tubal rank tensor com-pletion problem by convex surrogate function minimization.At the following, we show how to define the convex tensornuclear norm induced by the t-product ∗L. We can first de-fine the tensor spectral norm as in [15].Definition 2.7. (Tensor spectral norm) Let L be any in-vertible linear transform in (7), and A ∈ Rn1×n2×n3. Thetensor spectral norm of A is defined as ∥A∥ := ∥ ¯A∥.The tensor nuclear norm can be defined as the dual nor-m of the tensor spectral norm. To this end, we need thefollowing assumption on L given in (7), i.e.,L⊤L = LL⊤ = ℓIn3,(10)where ℓ > 0 is a constant. Using (10), we have the follow-ing important properties,⟨A, B⟩ = 1ℓ� ¯A, ¯B�,(11)∥A∥F = 1√ℓ∥ ¯A∥F .(12)For any B ∈ Rn1×n2×n3 and ˜B ∈ Rn1n3×n2n3, we have∥A∥∗ := sup∥B∥≤1⟨A, B⟩(13)= sup∥ ¯B∥≤11ℓ ⟨ ¯A, ¯B⟩(14)≤1ℓsup∥ ˜B∥≤1⟨ ¯A, ˜B⟩(15)=1ℓ ∥ ¯A∥∗,(16)where (14) uses (11), (15) is due to the fact that ¯B is a blockdiagonal matrix in Rn1n3×n2n3 while ˜B is an arbitrary ma-trix in Rn1n3×n2n3, and (16) uses the fact that the matrixnuclear norm is the dual norm of the matrix spectral norm.On the other hand, let A = U ∗L S ∗L V⊤ be the t-SVD ofA and B = U ∗L V⊤. We have∥A∥∗ =⟨U ∗L S ∗L V⊤, U ∗L V⊤⟩=⟨U⊤ ∗L U ∗L S, V⊤ ∗L V⟩=⟨S, I⟩=1ℓ ⟨ ¯S, ¯I⟩=1ℓ Tr( ¯S)=1ℓ ∥ ¯A∥∗.(17)59990图1：n1×n2×n3张量的t-SVD示意图。0算法2 基于t-乘积的T-SVD[9]输入：A∈Rn1×n2×n3和可逆线性变换L。输出：A的T-SVD分量U、S和V。01. 计算¯A = L(A)。02. 通过¯A计算¯U、¯S和¯V的每个前视面，方法如下：0for i = 1，∙∙∙，n3 do0[¯U(i), ¯S(i), ¯V(i)] = SVD(¯A(i))；0end for03. 计算U = L^(-1)(¯U)，S = L^(-1)(¯S)，V = L^(-1)(¯V)。0显然，对于适当的维度，A�LI = A和I�LA = A。张量¯I =L(I)是一个每个前视面都是单位矩阵的张量。0定义2.4.（正交张量）[9]设L是(7)中的任意可逆线性变换。如果张量Q∈Rn×n×n3满足Q��LQ=Q�LQ�=I，则称其为正交张量。0定义2.5.（f-对角张量）[10]如果一个张量的每个前视面都是对角矩阵，则称其为f-对角张量。Combining (13)-(16) and (17), we then have the followingdefinition of tensor nuclear norm.Definition 2.8. (Tensor nuclear norm) Let L be any in-vertible linear transform in (7) and it satisfies (10), andA ∈ Rn1×n2×n3. The tensor nuclear norm of A is definedas ∥A∥∗ := 1ℓ ∥ ¯A∥∗.If we define the tensor average rank as ranka(A) =1ℓ rank( ¯A), then it can be proved that the above tensor nu-clear norm is the convex envelope of the tensor average rankwithin the domain {A|∥A∥ ≤ 1} [15].minXτ∥X∥∗ + 12∥X − Y∥2F .(22)Let Y = U ∗L S ∗L V⊤ be the tensor-SVD of Y. For anyτ > 0, we define the Tensor Singular Value Thresholding(T-SVT) operator as followsDτ(Y) = U ∗L Sτ ∗L V⊤,(23)whereSτ = L−1((L(S) − τ)+),(24)where t+ denotes the positive part of t, i.e., t+ = max(t, 0).This operator simply applies a soft-thresholding rule toL(S), effectively shrinking these towards zero. The T-SVToperator is the proximity operator associated with the pro-posed tensor nuclear norm.600003.带有精确恢复保证的张量补全0在本节中，我们使用基于线性变换的张量核范数最小化来考虑低秩管状张量补全问题。设L是(7)中的任意可逆线性变换，满足(10)。设M∈Rn1×n2×n3是一个未知张量，它的管状秩rankt(A)=r。假设M的条目独立地以概率p观察到。观察到的条目的索引集合被表示为Ω。在这个设置中，我们表示Ω�Ber(p)。因此，张量补全问题是从观测到的条目{Mij,(i,j,k)∈Ω}中恢复出底层低秩管状张量M。在这项工作中，我们通过以下基于提出的张量核范数的凸问题来解决张量补全问题。0min X∥X∥�，s.t. PΩ(X)=PΩ(M)。(18)0上述模型是凸的，因此最优解是可计算的。现在的问题是，我们如何通过求解(18)来精确恢复M？观察到，对于一个在几乎所有行或列中都等于零的低秩矩阵来说，恢复几乎是不可能的[3]。因此，引入不相干条件来避免这种病态情况。对于张量补全，我们遇到了同样的问题。为了避免M太稀疏的情况，我们需要以下标准的张量不相干条件。0max i=1,∙∙∙,n1∥U��L˚ei∥F≤µr0n1ℓ，(19)0max j=1,∙∙∙,n2∥V��L˚ej∥F≤µr0n2ℓ，(20)0其中µ>0，˚ei是下面定义的张量基。0定义3.1（标准张量基）设L是(7)中的任意可逆线性变换，满足(10)。我们将˚ei表示为张量列基，它是一个大小为n×1×n3的张量，其中L(˚ei)的(i,1,1)处的条目等于1，其余条目等于0。自然地，它的转置˚e�i被称为行基。另一个标准的张量基称为管基˙ek，它是一个大小为1×1×n3的张量，其中L(˙ek)的(1,1,k)处的条目等于1，其余条目等于0。0在接下来的内容中，我们将n(1)=max(n1,n2)表示为0n(2)=min(n1,n2)。那么ℓ≤µ≤n(2)ℓ0r .0定理3.1。设L是(7)中的任意可逆线性变换，满足(10)，M∈Rn1×n2×n3，其管状秩rankt(M)=r。设M=U�LS�LV�是M的瘦t-SVD。假设索引Ω�Ber(p)，并且张量不相干条件(19)-(20)成立。存在普遍常数c0，c1，c2>0，使得如果0p ≥ c0µrl0n(2)ℓ，(21)0那么M是满足至少1-c1(n1+n2)-c2概率的(18)的唯一解。0理论上，定理3.1表明凸问题(18)的最优解ˆX可以精确恢复底层低秩管状张量M。特别地，为了以高概率恢复一个张量M∈Rn1×n2×n3，采样复杂度为O(rn(1)n3log2(n(1)ℓ))。这个界限与底层张量M的自由度O(rn(1)n3)相比是紧密的。注意，上述结果进一步推广了现有的低秩张量和低秩矩阵补全结果。例如，当离散傅里叶变换矩阵被用作可逆线性变换L时，t-乘积�L简化为[10]中的t-乘积，因此在定义2.8中提出的张量核范数简化为[14]中的张量核范数。然后，定理3.1中的结果等价于[16]中的恢复保证。此外，如果M是一个矩阵，定理3.1简化为[5]中的恢复保证。问题(18)可以通过标准的交替方向乘子法(ADMM)来解决[12]。我们省略ADMM的细节，但给出ADMM中以下关键子问题的解决细节，即对于任何Y∈Rn1×n2×n3，Table 1: Exact tensor completion on random data. The DiscreteCosine Transform (DCT) is used as the linear transform L.X 0 ∈ Rn×n×n, r = rankt(X 0), m = pn3, dr = r(2n − r)nnrmdrprankt( ˆX)∥ ˆX−X∥F∥X∥F50340.4733.5e−650530.5753.1e−650820.5984.2e−6501020.72103.1e−6100540.3951.1e−51001030.57109.9e−61001520.56156.8e−61002020.72203.8e−6200540.2056.2e−52001030.29104.8e−52002020.38204.7e−52003020.56301.9e−5Theorem 3.2. Let L be any invertible linear transformin (7) and it satisfies (10).For any τ > 0 and Y ∈Rn1×n2×n3, the tensor singular value thresholding oper-ator (23) obeysDτ(Y) = arg minXτ∥X∥∗ + 12∥X − Y∥2F .(25)The main cost of ADMM for solving (18) is to computeDτ(Y) for solving (25). For any general linear transfor-m L in (7), it is easy to see that the per-iteration cost isO(n1n2n23 + n(1)n2(2)n3). For some specific linear trans-forms, e.g., DFT, the per-iteration cost can be further re-duced. The cost can be further reduced by taking the low-rank structure priori of M as the matrix case in [12].4. ExperimentsIn this section, we conduct numerical experiments to cor-roborate our main results. We first investigate the abilityof the convex program (18) to recover tensors with varioustubal ranks and sampling rates. We then apply it for imagerecovery and compare the performance with existing low-rank matrix and low-rank tensor completion models2.4.1. Exact Recovery on Random DataWe conduct two experiments to demonstrate the prac-tical applicability of the tensor nuclear norm heuristic forrecovering low-rank tensors. We first verify the correct re-covery guarantee in Theorem 3.1. Note that Theorem 3.1holds for any invertible linear transform L with L in (7) sat-isfying (10). We consider two cases of L: (1) Discrete Co-sine Transform (DCT) [9]; (2) Random Orthogonal Matrix(ROM)3. In both cases, (10) holds with ℓ = 1. We simplyconsider tensors of size n × n × n, with n = [50, 100, 200].We generate a tubal rank r tensor by M = P ∗L Q, where2Codes of our method: http://github.com/canyilu.3Codes:https://www.mathworks.com/matlabcentral/fileexchange/11783-randorthmat.Table 2: Exact tensor completion on random data. A RandomOrthogonal Matrix (ROM) is used as the linear transform L.X 0 ∈ Rn×n×n, r = rankt(X 0), m = pn3, dr = r(2n − r)nnrmdrprankt( ˆX)∥ ˆX−X∥F∥X∥F50340.4733.6e−650530.5753.0e−650820.5984.4e−6501020.72101.3e−6100540.3951.5e−51001030.57109.7e−61001520.56157.0e−61002020.72203.9e−6200540.2055.8e−52001030.29104.6e−52002020.38204.7e−52003020.56302.0e−560010P ∈ Rn×r×n和Q ∈ Rr×n×n的元素是独立从N(0,1/n)分布中采样得到的。然后我们从M中均匀采样m =pn^3个元素作为已知项。一个有用的参考量是dr = r(2n -r)/n。通过PΩ(M)，我们求解（18）并得到解ˆX。然后我们报告ˆX的管积秩和相对误差∥ˆX -M∥F/∥M∥F。表1和2分别给出了两种不同线性变换L的恢复结果。可以看出，凸规划（18）在所有情况下都给出了M的正确秩估计，并且相对误差很小。因此，这些结果很好地验证了定理3.1中声称的凸规划（18）的正确恢复保证。定理3.1展示了基于秩t(M)和采样率p的不相干张量的完美恢复。现在我们考察M的管积秩和采样率p变化时的恢复现象。我们以与上述实验相同的方式生成M ∈ Rn×n×n，其中n =50。然后我们均匀采样m =pn^3个元素作为已知项。我们设置p = [0.01:0.01:0.99]，r= [1, 2, ..., 38]。对于每个（r,p）对，我们模拟10个测试实例，并在恢复的ˆX满足∥ˆX -M∥F/∥M∥F ≤10^-3时宣布试验成功。图2绘制了每个（蓝色=0%，黄色=100%）对应的正确恢复比例，对应不同线性变换L的选择。可以看出，两种情况下的恢复现象非常相似。两者都有一个大的区域中恢复是正确的。这验证了我们在定理3.1中的主要结果，即当性质（10）成立时，恢复保证对不同线性变换的选择是不变的。我们的结果也与现有的低秩矩阵补全[3,5]和低秩张量补全[16]中的现象一致。04.2. 图像恢复的张量补全00.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9p3530252015105r00.20.40.60.810.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9p3530252015105r00.20.40.60.81(b) random orthogonal matrixcan be well approximated by low-rank matrices on the threechannels independently. If we treat a color image as a threeway tensor, then it can be well approximated by low ranktensors. There have many works which use such observa-tions, e.g., [13, 28, 14, 15, 7], for image recovery.Note that the t-product induced tensor nuclear norm isorientation dependent. The recovery performance may bedifferent for different tensors constructed from a color im-age. For a color image with size h × w, we can construct atensor M ∈ Rh×3×w, where the lateral slices correspondto the three channels4. We randomly set m = 3phw entriesto be observed, where we use p = 0.3 in this experiment.We consider four methods for image recovery and comparetheir performance: (1) LRMC [3]: low-rank matrix com-pletion applied on each channel of images separably; (2)LRTC [13]: low-rank tensor completion model in (2); (3)TNN [16]: tensor nuclear norm (TNN) based tensor com-pletion model (a special case of our model (18) by using thediscrete Fourier transform as the linear transform L); (4)TNN-DCT: our TNN minimization model (18) by using theDiscrete Cosine Transform (DCT)5 as the linear transformL; (5) TNN-ROM: our TNN minimization model (18) byusing the Random Orth