在线高秩矩阵完备化模型的时间复杂度及优势分析

8690时间复杂度为O（n），时间复杂度为O（r）。IJJ：在线高秩矩阵完备化Jicong Fan，MadeleineUdell Cornell UniversityIthaca，NY 14853，USA{jf577，udell}@ cornell.edu摘要最近的进展，在矩阵完成使数据imp- tation在满秩矩阵，利用低维（非线性）的潜在结构。本文提出了一种新的高秩矩阵完备化模型（HRMC），结合批量和在线方法来拟合模型，并采用样本外扩展来完备新数据。该方法利用核技巧将数据隐式映射到一个高维多项式特征空间;重要的是，即使原始数据矩阵是满秩的，数据也占据该特征空间中的低维子空间。该在线方法可以处理流数据或序列数据，适应非平稳的潜在结构，并且具有比以前的HRMC方法更低的空间和时间复杂度例如，时间复杂度[6，24]，图像修复和分类[1，10]。所有上述LRMC和HRMC方法都是离线方法。然而，对于许多问题，我们每次获得一个样本，并希望在每个新样本到达时使用在线优化来更新模型。此外，与离线方法相比，在线方法[25，21，29]通常具有较低的空间和时间复杂度，并且可以适应潜在数据结构的变化由于这些原因，在线矩阵完成最近得到了越来越多的关注[2，5，15，19]。2. 相关工作和我们的贡献在线完成矩阵。孙和罗[26]和金等人。[14]提出使用随机梯度下降（SGD）来解决低秩因子分解（LRF）问题3 3最小化. X−UV2，变量U∈r是特征空间中的矩阵秩，并且rn。我们还提供了这些方法成功所需的采样率的指导。在合成数据和运动数据上的实验结果验证了所提方法的性能。1. 介绍在过去的十年中，低秩矩阵完备化（LRMC）得到了广泛的研究[4，16，22，23，20，13，3，18，9]。例如，Can de s和Recht[4]证明了n个秩为r的yn×n非相干矩阵可以从Cn 1中精确恢复. 通过求解核范数最小化（NNM）的凸问题，得到了高概率的2rlogn均匀随机抽样项.然而，LRMC不能恢复高秩或满秩矩阵，即使当数据位于低维（非线性）流形上为了解决这个问题，最近一些研究人员开发了新的高秩矩阵完成（HRMC）方法[8，17，28]，用于从多个子空间[7，6，11]或非线性模型[1，24，10]中提取的数据这些HRMC方法在处理丢失数据的子空间聚类、运动数据恢复等实际问题时，性能优于LRMC方法Rm×r，V ∈Rn×r，其中X∈Rm×n，X的观测条目的位置。具体地，给定条目Xij，通过梯度下降来更新U的第i行和V的第jYun等人[29]研究了当矩阵的列顺序呈现时的流或在线矩阵完成问题在[2]中提出的GROUSE方法使用子空间的格拉斯曼流形上的增量梯度下降来在线学习不完整数据的低秩分解。这些在线方法有一个共同的局限性：它们不能恢复高秩矩阵。Mairal等人[21]还研究了以学习字典对于稀疏编码：最小化1<$x−Dα<$2+λ<$α<$1。 一D∈C， α2基于稀疏分解的矩阵完备化算法，在[11]中提出通过结合[21]和[11]的思想，可以在线恢复高秩高阶矩阵完成。Elhamifar [6]提出利用群稀疏约束完成由低维子空间的并集数据组成的Alameda-Pineda等人[1]提出了一种用于分类的非线性矩阵完备化方法。所述方法对由（非-（i，j）∈Ωi：8691.概率1，rank（X）=min{m，n，}。ppD+p.Rank（X）=min{m，n， }..概率为1的矩阵，rank（φ（X））=min{m<$，n，}。PQ.Σd+pq1.其中A∈，Z∈，r=。的MQPQPQ我minm<$，n =D+p.Σi1d|µ| ≤p线性）特征-标签对，其中未知标签被视为缺失条目。该方法不适用于一般的矩阵完备化问题，随 机 系 数 多 项 式 例 如 ， 当 d=2 且 p=2 时 ， 对 于i=1，. . . ，m，xi=cis<$，其中ci∈R6且s<$=[1，s1，s2，s2，s1s2]<$. 引理1显示 1 2不一定在单个块中Ongie等人[24]假设X由代数簇给出，提出了一种通过最小化φ（X）的秩来恢复X的缺失项的方法，其中φ（X）是由多项式核给出的特征矩阵Fan和Chow[10]假设数据来自非线性潜变量模型，并提出了一种非线性数学完备化方法（NLMC），该方法使φ（X）的秩最小化，其中φ（X）由多项式核或RBF核诱导的高维非线性特征组成。HRMC面临的挑战。首先，现有的HRMC方法缺乏强有力的理论保证，恢复所需的样本复杂度。例如，在VMC中，作者仅对低阶多项式核提供了采样率的下界（ρ0，[24]的等式（6）），并且由于代数多样性假设，ρ0涉及未知参数R 在NLMC [10]中，作者仅提供了采样率的粗略下限，即p> O（d/m），其中d是隐变量的维数。第二，现有的HRMC方法不能扩展到大型矩阵。例如，VMC和NLMC要求在每次迭代中对n×n核矩阵进行奇异值分解. 的[6]的方法也不是有效的，因为稀疏操作。当p很大时，X的秩很高引理1. 假设X的列满足（1）。然后用D+pp证据 展开多项式f i，对于每个i = 1，. . . ，m写xi=fi（s）=c<$s<$$>，其中s<$={sµ1···sµd}且c∈R （ d+p ） . X 的每 一 列 满 足 x=Cs<$， 其 中 C=[c1· · ·cm]∈Rm×（）的情况。矩阵X可以写成-10为X=CS<$ ，其中S<$=（s<$1，. . . ，s<$n）∈R（p ）×n. 变量s是不相关的，系数c是随机的，所以一般来说C和S都是满秩的。因此D+pp在本文中，我们的目标是恢复X从一些随机采样项目，我们表示为{Mij}（i，j）∈N。 当p很大时，X一般是高秩的，不能用传统的LRMC方法恢复。备注。在本文中，我们使用术语设φ：Rm→Rm<$是一个q阶多项式特征映射φ（x）={xµ1···xµm}|µ|≤q。 这里m<$=m+q。写n×n系数矩阵的最小化第三，现有的HRMC方法没有样本外扩展，这意味着它们不能有效地完成新数据。最后但并非最不重要的是，现有的HRMC方法是离线方法，不能处理在线数据。捐款. 在本文中，我们旨在应对这些挑战。提出了一种新的基于核分解的高秩矩阵完备化方法。KFMC比最先进的方法更有效和准确。其次，我们提出了一个在线版本的KFMC，它可以大大优于在线LRMC。第三，我们提出了KFMC的样本外扩展，这使我们能够使用预先学习的高秩模型来计算。φ（X）= [φ（x1），φ（x2），· · ·，φ（xn）]并考虑其秩：定理1. 假设X的列满足（1）。然后d+pqPQ证据定义pq阶多项式映射f（s）：=φ（x）=φ（f（ s ） ） . 如 上 所 述 展 开 ， 写 出 向 量 φ （ x ）=1，. . . ，sn）∈R（pq ）×n. 如前所述，k和S是一般满秩的，所以ran k（φ（X））=min{m<$，n，d+pq}的概率为1。当rank（φ（X））≥ rank（X）时，定理1证明了当d很小时，n很大时，φ（X）是一般低秩的例如，当d= 2，m= 20，n= 200，p= 4，并且直接填充新数据。 最后，我们分析了抽样KFMC成功所需的利率。q= 2，一般rank（X）min{m，n} = 0。75whilerank（φ（X））- -3. 方法3.1. 高秩矩阵我们假设X∈Rm×n的列由下式给出：0的情况。225：X是高阶，但φ（X）是低阶。3.2. 核分解为了恢复X的缺失条目，我们建议求解minimizeX，A，Z1<$φ（X）−AZ<$22F（2）x=f（s）= [f1（s），f2（s），· · ·，fm（s）]n，（1）其中s ∈ Rd（d <$1以获得数值稳定性并定义更新（五）RBF：k（x，y）= exp. −1x−y<$2，D：= 1g D H−1。（八）超参数c，q和σPoly和RBF的（隐式）特征映射φ（x）分别是q阶和无限阶多项式映射.重写（4）以定义核分解矩阵完备化（KFMC）minimizen（Z，D，X）∆86932.Σ我们对D的更新的有效性是由lemma之后(The引理的证明和关于τ的作用的讨论在补充材料中。）引理3. 更新（8）是松弛的牛顿X、 D、 Z服从Xij=Mij，（i，j）∈（KFMC）（Z，D −式中，n（Z，D，X）=1TrKXX−2KXD Z+Z<$KDDZ+αTr（K DD）+β<$Z<$2。对于RBF核，Tr（KDD）=Tr（K DD）2τD D对于RBF核，梯度为2 2F是一个常数，可以从目标中删除。∇ n=1（XQ−DΓ）+2（DQ− DΓ）。（九）Dσ21 1σ22 28694^τσ2n^^^n∈n2[X]<$，D，Z2NF2<$X：=τ<$X<$（σ2（2Q4−Γ3−2Γ4））njωjn^ ^您的位置：8：计算时间X 使用（12）或（14）（在整个过程中，我们滥用符号来写（Z，D，X）。这里Q1=−ZK XD，Q2=（0. 5ZZ+ 0. 5αIr）I算法1离线KFMC输入：M，λ，r，k（·，·），α，β，tmax，ηKDD，Γ1=diag（1<$Q），且Γ=diag（1<$Q），其中n1 2r21R和11：初始化：t=0，X，D<$N（0，1），N^D=0，N^X=02：重复引理（在补充材料中证明）表明，如果σ和n足够大，则（9）中的XQ1与DΓ1、DQ2和DΓ2相比几乎是常数引理4. <$X（Z<$$>K）−X（Z<$$>K）<$≤σ<$n<$X <$2 <$D1− D2 <$F，其中c是一个小常数。3：t←t+ 14：Z=（KDD+βIr）−1KXD5：使用（8）或（10）计算CXD6：η^D=ηη^D+η ^DXD1CXD2F7：D←D−^D因此，我们可以计算一个近似的Hessian ne-收集XQ1. 在（8）中，我们定义图9： X=ηX+X10：X←X−<$X且Xij=Mij<$（i，j）∈<$11：直到收敛或t=tmaxD：=1mmD第二季度（1-Γ1-2Γ2））−1.（十）输出：X、D更新X。最后，固定Z和D，我们希望在X上最小化（KFMC），这也没有封闭形式的解决方案。同样，我们建议使用放松的牛顿方法X <$X− <$X来更新X。对于多项式核，gX=X（W3<$In）−D（W4<$<$Z）（十一）3.4. 在线KFMC假设我们在时间t得到一个不完整的样本x，需要及时更新矩阵补全模型或在线求解优化。在（4）中，我们可以直接将约束条件代入目标函数中，得到以下等价问题=qX Z），n其中W=<$X <$X+c<$q−1，W=XD+cq−1最小化<$1<$φ（xj）−φ（D）zj<$2+α<$φ（D）<$2+β<$zj<$2，1m∈ Rm由1s组成，且w∈ Rm由j=1（十六）W3的对角线条目。如上，我们定义其中[X]表示X的未知条目。表示X：=1g X（十二）（[x]，D）：=min1<$φ（x）−φ（D）z<$2τjωjz，[x]2jj当使用RBF核时，我们得到jjω<$j+ α<$φ（D）<$2+β<$zj<$2，D1=1（DQ- XΓ）+2（XQ-Xr）。（十三）2nF2（十七）Xσ233σ24 4其中[xj]ωj（[xj]ω<$j）表示观测值（未知）en-这里Q3=−Z<$KX<$D，Q4=0。5InKXX，Γ3=xj和ωj的tries（ω<$j）表示相应的位置。然后（16）最小化经验成本函数diag（1<$Q3），且Γ4= diag（1<$Q4）。 如（10）中，定义R n1 1−1g（D）：= 1π（[x]，D）.（十八）j=1这里的计算成本实际上并不高，因为要求逆的矩阵是对角矩阵。我们也可以使用动量更新来加速D和X的收敛：预期成本为g（D）：=E[x]ω [X（[x]ω，D）] =limn→∞g n（D）. （十九）. ^D<$η为了近似地最小化（19）在线，我们提出以下建议：对给定的不完全样本x进行降阶优化（十五）ˆ12<$X<$η<$X+<$X，X<$X −<$X其中0<η1是常数。 优化方法minimize（z，[x]ω<$，D）：=r∈Rr都是由1组成以下3、4.（十四）∆86952φ（x）−φ（D）z[x]ω<$，D，z+αφ（D）2+ βz2。（二十）总结为算法1。下面的引理（在补充中有证明）表明该方法收敛。引理5. 对于足够小的η，算法1收敛2F2在随机初始化D的情况下，我们首先通过交替最小化z（z，[x]ω<$，D）来计算z和[x]ω<$，其等式为：到一个固定点。最小化1k-k z+1zKz+ β<$z<$2。 （二十一）[x]ω<$，z2xx xD2DD28696XDτwR^^σ2xτγx22τ具体地，在每次迭代中，z被更新为z=（K DD+ βIr）−1k。（二十二）我 们 建 议 用 牛 顿 的 方 法 来 更 新 [x]ω′ ， 即 ，[x]ω<$[x]ω<$−[x]ω<$。当使用多项式核时，我们得到x然后x=1（二十四）1当使用RBF核时，我们有<$x<$$> =1（Dq−γx），（25）其中q=−z<$kx<$D且γ=1<$q。然后= σ2（二十六）与离线KFMC类似，我们也使用动量来加速在线KFMC的优化算法2中总结了优化步骤。 在线矩阵补全的误差可以通过多遍优化或增加样本数来减小。 在算法2中，在（17）中定义的序列ωt（[xt]ωt，D）可以不连续地减小，因为不完整的样本xt可以引入高的不确定性。然而，序列g t（D）（在（18）中定义的经验成本函数）是收敛的，因为对于j=1，···，t，通过优化[x j] ω< $j，zj和D来最小化ω（[ x j]ω j，D）。算法2在线KFMC输入：不完整样本{[x1]ω1，[x2]ω2，· · ·，[xt]ωt}，r，k（·，·），α，β，niter，η，npass1：初始化：DN（0，1），D=0第二章： 对于u= 1到n，通过do3：对于j= 1到t，4：l=0，X=0，C=（KDD+βIr）−1（24）和（26）的推导与（8）和（10）的推导相似。然后我们重复（22）-（26）直到收敛。在计算z和[x]ω<$之后，我们通过min计算D最小化ωn（z，[x]ω<$，D），其等于5：重复6：l←l+1和zj=CkX<$D7：使用（24）或（26）计算px8：^x←η^x+x最小化−k xD z+1z<$K DD z+ αTr（K DD）。 （二十七）D9：[xj]ω<$j←[xj]ω<$j−[x]ω<$j10：直到收敛或l=niter11：使用（29）或（31）计算CXD我们建议使用SGD来更新D，即，D←D−D。图12：^D←η^D+D和D←D−^D当使用多项式核时，我们有D（二十八）其中w1=<$x<$D+c<$q−1，W2=<$D<$D+c<$q−1。然后我们有13：结束14：结束输出：Xt= [x1，x2，· · ·，xt]，D3.5. KFMC的样本外扩展D=1中文（简体）2+αW2 Ir2。（二十九）从离线矩阵完成获得的矩阵D(1) 或在线矩阵完成（2）可用于恢复这里我们不能使用（8）的方法，因为zz不如ZZ稳定。此外，以下引理（在补充材料中证明）确保了更新D的有效性：引理6.将D更新为D−D不会发散，ℓˆ(z,[x],D−∆)−ℓˆ(z,[x],D)≤−1ǁ∇ℓˆǁ2pr o-新数据的缺失条目而不更新模型。我们也可以从完整的训练数据中计算D：相应的算法类似于算法1和2，但不需要X更新。我们可以通过求解来完成一个新的（不完整的）样本xnew。minimize1<$φ（xnew）−φ（D）8697τσ2znew<$2+β<$znew<$2，（32）ω<$Dω<$2ττ0DF[xnew]ω<$新 ，znew 22证明了τ>1，其中τ0=αzz<$W2+αW2 <$Ir<$2。当使用RBF核时，导数为其中[xn ew]ω<$n e w表示xn ew的未知条目。KFMC的样本外扩展显示为算法3。∇ℓˆ=1(xQ-Dr）+2（DQ −DΓ），（30）Dσ211σ22 23.6. 复杂性分析其中Q1= −zk XD，Q2=（0. 5zz+ 0。5αIr）IKDD，Γ1=diag（Q1），且Γ2=diag（1<$rQ2）. 类似于（29）和引理6，我们得到D=1（三十一）考虑由（1）给出的高（偶数，满）秩矩阵X∈Rm×n（m<$n） 在VMC、NLMC和我们的KFMC方法中，存储的最大对象是核矩阵K ∈ Rn×n。所以它 们 的 空间 复 杂 度 都 是O （ n2 ） 。 在 VMC 和NLMC中，主要的计算步骤是8698^p^Q.r=u。因此，当d很小时，n很大，φ（X）.当rank（φ（X））=u.PQQ我k=1我（q+1）！^ ^您的位置：（q+1）！）的情况。这一论点.Σ.Σ。Σ算法3KFMC的样本外扩展输入：D（根据训练数据计算），k（·，·），β，niter，η，新的不完整样本{[x1]ω1，[x2]ω2，···，[xt]ωt}1：C=（KDD+βIr）−12：对于j= 1至t，3：l= 0，x=04：重复5：l←l+1和zj=CkxD6：使用（24）或（26）计算pxk= 1，. . . 、u. 为了方便起见，我们写X= [X{1}，X{2}，· · ·，X{u}]，（34）其中每个X{k}的列都在f{k}的范围内，尽管我们不知道X的每个列是从哪个子空间中提取的类似于引理1的论证表明rank（X）=min{m，n，u. d+p}（35）7：x←ηx+x8：[xj]ω<$j←[xj]ω<$j−[x]ω<$j9：直到收敛或l=niter10：结束输出：Xnew= [x1，x2，· · ·，xt]空间复杂度时间复杂度VMCO（n2）O（n3+mn2）NLMCO（n2）O（n3+mn2）KFMCO（n2）O（mn2+rmn）OL-KFMCO（mr+r2）O（r3）OSE-KFMCO（mr+r2）O（mr）表1：时间和空间复杂度（X∈Rm×n，m<$n）在每次迭代中计算K及其奇异值分解时间复杂度为O（n2+n3）。在我们的KFMC中，主要的计算步骤是形成K，对（6）中的r×r矩阵求逆，以及将m×n和n×r矩阵相乘以计算导数。 因此，时间复杂度为O（ mn2+r3+rmn ） = O （ mn2+rmn ） ， 因 为n<$r。在线KFMC不存储内核矩阵K。相反，存储的最大对象是D和KDD。因此，空间复杂度为O（r2）。主要计算概率为1，所以当u或p很大时，X很可能是高秩或满秩的我们 可以 推广 定理 1 ， 证明rank （ φ （ X ） ）=min{m<$，n，r}的概率为1，其中m<$=m+q和d+pqpq是低秩的，所以X的缺失条目仍然可以被恢复通过本文提出的离线和在线方法特别地，对于从线性子空间的并集（p= 1且u >1）中提取的数据，一般地rank（X）= min（m，n，ud）D+QQ3.8. 于采样率假设X由公式33生成，并且观察到其条目的比例ρKFMC我们提供了一些技巧来帮助决定应该观察多少个条目来完成多项式和RBF内核。（36）和（37）的详细计算将推迟到补充部分。为了使用q阶多项式核唯一地完成φ（X），一个经验 法 则 是 观 察 到 的 条 目 的 数 量 应 该 至 少 与 矩 阵 φ（X ）中 的 自 由 度 的 数 量 一 样 大 [24]。这里， φ（X）是秩r=ud+pq的m<$×n矩阵，其中m<$=m+q。我们计算具有该秩的矩阵的自由度，以证明采样率应满足步骤是求r×r矩阵的逆（参见算法2）。时间复杂度为O（r3）。在样本外扩展中，ρKFMC ≥。r/n+r/m<$−r2/n/m<$1/q。（三十六）存储的最大对象是D和C（见算法3），因此空间复杂度为O（mr+r2）。对于每个在线样本，我们只需要将m×r矩阵与向量相乘。时间复杂度为O（m）。该分析总结见表1。我们看到，所提出的三种方法的空间和时间复杂度都大大低于VMC和NLMC。3.7.子空间并的推广KFMC还可以处理从子集合中提取的数据，空间. 假设X∈Rm×n的列由下式给出：方程（36）限定了自由（2）考虑到它的大小和大小。当然，φ（X）是X的确定性函数，它的自由度要少得多。因此，虽然公式36提供了一个很好的经验法则，但我们仍然希望较低的采样率可能会产生合理的结果。对于RBF核，q= ∞，因此条件（36）是真空的。然而，RBF核可以很好地近似多项式核，我们有φ（x）=φ（x）+O（.cq+1 ），（37）{x{k}=f{k}（s{k}）}u、（三十三）其中φi（x）表示q阶多项式核的第i个特征其中s{k} ∈Rd（d<$m n）是随机变量，内尔因此，对φ∈i（x）的精确覆盖意味着近似.cq+1f{k}：Rd→Rm是p阶多项式函数，10. A. B. C.D.E.C.D.E.8699.X（p+1）！pXp定义为RE=<$X−X<$F/<$X<$F[6]，其中X表示提供了RBF核应该恢复的直观性cq+1映射.该模型可以重新表述为x=Pz，其中P∈R30×（（3+p）−1），P<$N（0，1），z由以下组成：假设（36）成立。当然，我们可以通过考虑完整矩阵φ（X）的第一块来识别X的缺失项。在实验中，我们观察到RBF核往往比多项式核更好。我们假设RBF核的有效性有两个原因：1）它捕捉了φ（x）中的高阶特征，当n很大时，这是有用的。2）它更容易分析和优化，加快收敛速度。低秩矩阵完备化方法只能在给定采样率的情况下唯一地完备矩阵，该采样率满足s的多项式特征。考虑以下情况：• 单非线性子空间设p= 3，生成一个P和100s。则X∈R30×100的秩为19。• 非线性子空间的并集设p= 3，生成3个P，对每个P生成100s。则X∈R30×300的秩为30。• 线性子空间的并集设p= 1，生成10个P，对每个P生成100个s。 则X ∈R30×1000的秩为30。我们随机移除ρLRMC >。（m+n）rX─r2元╱百万，（38）矩阵，并使用矩阵完成来恢复丢失的条目。用相对误差来评价系统的性能其中r=min{m，n，u. d+p}。这个界限可以是vacu-^^u（大于1），如果u或p很大。相比之下，ρKFMC给出在相同的状态下，如果n足够大，则（36）仍然可以小于1。例如，当m= 20，d= 2，p= 2，u= 3时，我们有ρLRMC>0。91. 让q= 2，n= 300，则ρKFMC>0。五十六如果p= 1，u= 10，则ρLRMC>1，ρKFMC>0。六十四这一计算为我们的方法如何恢复高秩矩阵而经典的低秩矩阵完成方法失败提供了进一步的直观3.9.解析函数与光滑函数首先，我们假设f是有限阶多项式函数.然而，当f是解析函数或光滑函数时，我们的方法也有效。解析函数可以用多项式很好地近似。此外，光滑函数至少在区间上可以用多项式函数很好地逼近.因此对于光滑函数h：Rd→Rm，我们考虑生成模型x=h （ s ） =f （ s ） +e（ 39）其中f是h的p阶泰勒展开式，e∈ Rm表示残差，其标度为e∈O（c），其中恢复矩阵。如图1所示，LRMC方法的误差，即[ 26 ] LRF [26]和NNM [4]都相当高。相比之下，HRMC方法，特别是我们的KFMC具 有 显 着 较 低 的 恢 复 错 误 。 此 外 ， 我 们 的 KFMC（Poly）和KFMC（RBF）比VMC [24]和NLMC [10]更有效，其中已执行随机SVD [12图2显示了在线矩阵补全的结果，其中OL-DLSR（字典学习和稀疏表示）是我们从[21]和[11]修改的在线矩阵补全方法，并在我们的教程材料中详细介绍。我们看到，我们的方法OL-KFMC明显优于其他方法图3显示了HRMC的样本外延伸（OSE）的结果，其中我们的OSE-KFMC优于其他方法。有关实验/参数设置和分析的更多详细信息，请参见补充材料。c是h的p+ 1阶导数。我们看到，多项式模型的误差e随着p的增加而减小。为了拟合p更大的模型，界限（36）表明我们需要更多的样本n。我们猜想，对于任何光滑的h，只要n是足够的，就有可能以任意低的误差恢复丢失的条目。非常大。4. 实验4.1. 合成数据我们通过x=f（s）生成X的列，其中s∈ U（0，1），f：R3→R30是p阶多项式图1：合成数据（2）在（1）中，（2）是（（q+1）！）8700图2：合成数据图3：合成数据上矩阵完成的样本外扩展4.2. Hopkins 155数据与[24]类似，我们考虑了不完整数据的子空间聚类问题，其中Hopkins 155 [27]的缺失数据通过矩阵完成恢复，然后执行SSC（稀疏子空间聚类[7]）进行LRMC方法，而在线方法优于离线方法。一个原因是数据的结构随时间变化（对应于不同的运动），在线方法可以适应这种变化。将图5与[6]的图4进行比较，我们发现VMC、NLMC和我们的KFMC优于[6]中提出的方法此外，我们的OL-KFMC特别是与RBF核是最准确的。关于计算成本，毫无疑问，线性方法包括LRF，NNM，GROUSE和DLSR比其他方法更快。因此，我们仅在表2中显示了非线性方法的计算成本以进行 比 较 （ 已 在 VMC 和 NLMC 中 执 行 了 随 机 SVD[12]）。我们的KFMC比VMC和NLMC快，而我们的OL-KFMC比所有方法快至少10倍。图5：CMU运动捕捉数据恢复我们考虑两个下采样的视频序列，1R2RC和1R2TCR，每个都由6个帧组成。10次重复试验的平均聚类误差[7]见图4。与VMC和NLMC方法相比，本文提出的基于RBF核的KFMC方法具有更高的精度和效率.图4：不完整数据4.3. CMU运动捕捉数据我们使用矩阵完成来恢复人体运动的时间序列轨迹（例如，奔跑和跳跃）。与[6，24]类似，我们使用CMU运动捕获数据集的受试者#56的试验#6，其形成高秩矩阵[6]。我们考虑两种情况下的不完全数据，随机缺失和连续缺失。关于实验设置的更多细节在柔软的材料中。10次重复试验的平均结果见图5。我们看到HRMC的方法-VMC370NLMC610KFMC（Poly）170KFMC（RBF）190OL-KFMC（Poly）16OL-KFMC（RBF）19表2：CMU运动捕捉数据5. 结论本文提出了一种新的高阶矩阵完备化方法--核分解因子矩阵完备化（KFMC），并给出了一个在线版本和一个样本外扩展，其性能优于现有方法.我们的数字证明了运动数据恢复的方法的成功。我们相信，我们的方法也将是有用的转导学习（分类），车辆/机器人/化学传感器信号去噪，recommender系统，和生物医学数据恢复。确认这项工作得到了DARPA奖FA 8750 -17-2-0101的部分支持。8701引用[1] Xavier Alameda-Pineda ， Elisa Ricci ， Yan Yan ， andNicu Sebe.使用非线性矩阵完成从抽象画中识别情感。在IEEE计算机视觉和模式识别会议论文集，第5240-5248页，2016年。1[2] 劳拉·巴尔扎诺，罗伯特·诺瓦克，本杰明·雷希特。从高度不完全信息中在线识别和跟踪子空间。在通信，控制和计算（Allerton），2010年第48届Allerton年会上，第704-711页。IEEE，2010。1[3] Srinadh Bhojanapalli和Prateek Jain。通用矩阵完成。第31 届 国 际 机 器 学 习 会 议 论 文 集 ， 第 1881-1889 页 。JMLR，2014年。1[4] 埃马纽埃尔·J 坎迪斯和本杰明·里希特。 通过凸优化实现精确矩阵计算数学基础，9（6）：717-772，2009。1、7[5] 查兰帕尔Dhanja l，罗马里奇戈德尔，和Ste'phanCl e' men campion.通过核范数正规化在线完成矩阵2014年SIAM国际数据挖掘会议论文集，第623-631页SIAM，2014年。1[6] Ehsan Elhamifar自表达模型下的高阶矩阵完备化和聚类。神经信息处理系统进展29，第73-81页，2016年。一、二、七、八[7] E. Elhamifar和R.维达尔稀疏子空间聚类：算法、理论和应 用 。 IEEE Transactions on Pattern Analysis andMachine Intelligence，35（11）：2765-2781，2013. 1、8[8] 布莱恩·埃里克森，劳拉·巴尔扎诺，罗伯特·诺瓦克。高阶矩阵补全。在Artificial Intelligence and Statis-tics，第373-381页，2012年。1[9] Fan Jicong和Tommy W.S.周梁淑用最小二乘、低秩和稀疏自表示完成矩阵。Pat-tern Recognition，71：290-305，2017. 1[10] Fan Jicong和Tommy W.S.周梁淑非线性矩阵完备化。模式识别，77：378- 394，2018。一、二、七[11] J. Fan，M. Zhao和T. W. S.周梁淑通过稀疏因子分解完成矩阵，通过加速邻近交替线性化最小化解决IEEETransactions on Big Data，第1-1页，2018年。1、7[12] N. Halko，P. G. Martinsson和J. A.特罗普寻找随机结构：构造近似矩阵分解的概率算法。SIAM Review，53（2）：217-288，2011. 七、八[13] 莫里茨·哈特理解矩阵完备化的交替最小化。计算机科学基础（FOCS），2014年IEEE第55届年度研讨会，第651IEEE，2014。1[14] Chi Jin，Sham M Kakade，and Praneeth Netrapalli. 通过非凸随机梯度下降可证明有效的在线矩阵完成神经信息处理系统的进展，第4520-4528页，2016年。1[15] 贾亚·卡瓦莱，洪H·布伊，布拉尼斯拉夫·克维顿，龙·特兰·坦和桑杰·乔拉.高效的thompson采样在线矩阵分解推荐。神经信息处理系统的进展，第1297-1305页，2015年1[16] R. H. Keshavan，A. Montanari和S.哦从几个条目的矩阵完 成 。 IEEE Transactions on Information Theory ， 56（6）：2980-2998，June 2010. 1[17] 李春光和雷内·维达尔。 一个结构化稀疏加结构化低秩框架子空间聚类和完成。IEEE Transactions on SignalProcessing，64（24）：6557-6570，2016。1[18] 刘 光 灿 和 李 平 。 在 存 在 高 一 致 性 的 情 况 IEEETransactions on Signal Processing ， 64 （ 21 ） ： 5623-5633，2016。1[19] 布莱恩·洛伊斯和纳瑞塔·瓦斯瓦尼。在线矩阵补全与在线鲁棒主元分析。信息理论（ISIT），2015年IEEE国际研讨会，第1826IEEE，2015年。1[20] C. Lu，J. Tang，S. Yan和Z.是林书广义非凸非光滑低秩极小化。2014年IEEE计算机视觉和模式识别会议，第4130-4137页1[21] Julien Mairal，Francis Bach，Jean Ponce，and GuillermoSapiro.稀疏编码的在线字典学习。第26届机器学习国际年会论文集，第689-696页。ACM，2009年。1、7[22] Rahul Mazumder，Trevor Hastie，and Robert Tibshirani.学 习 大 型 不 完 全 矩 阵 的 谱 正 则 化 算 法 。 Journal ofMachine Learning Research，11（Aug）：2287-2322，2010. 1[23] Feiping Nie，Heng Huang，and Chris Ding.通过有效的schatten p-范数最小化恢复低秩在第26届AAAI人工智能会议上，第655-661页中国科学院出版社，2012年。1[24] 放大图片作者：Robert D.诺瓦克和劳拉·巴尔扎诺。高阶矩阵完备化的代数簇模型。第34届国际机器学习会议论文集，第2691PMLR，2017年。一二六七八[25] Steffen Rendle和Lars Schmidt-Thieme。大规模推荐系统中的在线更新正则化核矩阵分解模型。2008年ACM推荐系统会议论文集，第251ACM，2008年。1[26