矩阵低秩分解理论

所需积分/C币:17 2019-03-10 18:34:23 1.85MB PDF
收藏 收藏
举报

低秩分析,从稀疏表示到低秩矩阵,低秩矩阵表示的应用,最近发展等
从稀疏表示到低秩分解 矩阵低秩分解 十 Y E √矩阵低秩稀疏分解(Sρ parse and ow- rank matr iⅹ decomposition) 低秩矩阵恢复(Low- rank matrix recover y) 鲁棒主成分分析( Robust pr inc le component ana l ys i s,RPGA 低秩稀疏非相干分解(Rank- sparsity incoherence) 预备知识 定义1向量p范数。向量a=( )∈Rxl的 p范数为‖an=(∑1|a1P),其中p>0。 特殊地,当p=1时,‖a‖1=∑=1|a1|;当p=2时,‖a‖2= ∑121a2。此外,规定‖a‖。为向量a的非零元素的个数 a max a 1≤i≤n 定义2矩阵的内积。对于两个同型的m×n维实矩阵A 和B,它们的内积为A,B=∑m1=1anb5 定义3矩阵的范数。矩阵A=(an)n∈Rmx的 Robe nis范数为‖A|r=∑m:∑21a,0范数‖A。为矩阵A 的非零元素的个数,∞范数为A‖。=max|an,(1,1)范数 为A‖=∑n=1∑=1|a|.(2,1)范数为‖A‖21=∑=1 低秩矩阵恢复(鲁棒主成分分析RPCA) 在许多实际应用中,给定的数据矩阵D往往是低秩或近似低 秩的,但存在随机幅值任意大但是分布稀疏的误差破坏了原 有数据的低秩性,为了恢复矩阵D的低秩结构,可将矩阵D 分解为两个矩阵之和,即D=A十E,其中矩阵A和E未知, 但A是低秩的。当矩阵E的元素服从独立同分布的高斯分布 时,可用经典的来获得最优的矩阵A,即求解下列最优 化问题 min EF S t rank(A)sr, D=A+E A. 当E为稀疏的大噪声矩阵时,问题转化为双目标优化问题 mnin(rank(A),‖E‖。)s.t.D=A+E AE 引入折中因子入,将双目标优化问题转换为单目标优化问题 min rank(A)+A‖E‖as.t.A+E=D AE RPCA的求解 凸松弛 min rank(A)+A‖E‖os.t.A+E=D AE 难问题 松弛后 minA‖*+A‖E‖,!s.t.A+E=D AF 矩阵核范数‖A‖ =max trace (UTAV: UU=A, VV=L, 0. v 其中:n表示m阶单位矩阵; trace()表示矩阵的求迹算子。容 易证明矩阵A的核范数可用它的奇异值来表示,即‖A‖,= ∑1=1σ;,且当A满足‖A‖2≤1时,此范数是rank(A)的包络。 迭代阈值算法( iterative threshol ding,|T) 将最优化问题正则化,便得到优化问题 mIn ‖A‖,+A‖E‖1+p(‖A‖+E) AE S,tA+E=D 优化问题式的拉格朗日函数为 LA,E,Y)=‖A‖,+A‖E‖1,1+ (‖AP+‖En3)2+(Y,D-A-E 使用迭代阈值算法交替更新矩阵AE和Y。当EE,YY时, A+1= arg min L(A,Ek,Yk)= arg min‖A‖,/p+ A A A-Yl/2=D1(Y)=-D1(Y) 当A=A,Y=Y时,E1= arg min(A1,E,Y)= arg min a‖E1+ E E I E-Y/u F/2=S(Y/u)=u S(Y2) 当A=A 时,Y1=Y+62(D k+1 k+1 其中:步长δ满足0<8< ⅠT算法的迭代式形式简单且收敛,但它的收敛速度比较慢,且难以选取合适的步长 加速近端梯度算法( accelerated prox ima gradient, APG) 将优化问题式的等式约束松弛到目标函数中,得到如下的拉格朗日函 数:L(A,E,)=(‖A‖,+AE‖)+D-A-E/2 g( A, E, u) =u( l A.+A El1).(A, E)=D-A-E F/2 于是AE,μ)=gAE,)+fAE。画数gAE,)不可微,而f AE光滑且具有李普希兹连续梯度,即存在>,使得 ‖VfA,E)-VfA,E)lr≤ly(A-A,E-E) 其中:Vf(A,E)表示函数fAE关于矩阵变量A和E的 Creche t梯度。此处取2。对于给定的与D同型的两个矩阵Y和Y,作 LAE,μ)的部分二次逼近: Q(A, E, u, YA, YE)=g(A, E, u)+f(YA, YE)+ Vf(Y,Y),(A-Y4,E-Yg)+L1‖(A-Y4,E-YE)‖/2 g(A,E,)+fY4,Yg)+(Y4-(D-yg),A-Y4)+ KYE-(D-YA,E-YE+L A-YA /2+L F/2 加速近端梯度算法( accelerated prox ima gradient. APG 当E=E,Y4=Y4,Y=Y,A=p4时 A4+1= arg min Q(A,E,k,Y,Yg)= arg min u‖A‖,+ A A (YA-(D-YE), A)+L A-Y42/2= arg mInμk 1A,+lA-(Y+(D-Y-Y)/l)‖2= VL(YA+(D E 类似地,当A=A,y4=Y,Yg=Y,=k时 E+1amQ(A1,E,4,Y,Y)=+(D-Y-Y)/L) 为了得到更新YA和YE时的步长,需先确定参数t+:k+1=(1+√1+4t2)2 于是Y和Y的选代更新公式为:Y+1=A4+(14-1)(A2-Ak+1)14g+1 Yk+1=E4+(tk-1)(E k+1 )/t P+1 参数μ的迭代公式为k+1=max(mk,) 其中:L为事先给定的正数;0<η<1。 尽管APG与ⅠT算法类似,但它却大大降低了迭代次数。 对偶方法(DUL) ·由于核范数的对偶范数为谱范数,所以优化问题的对偶问题 为:max(D,ys.tJ(y)≤1 其中:J(Y=max(‖Y‖2,Y。);·表示矩阵元素绝对值最大 的值。当优化问题对偶式取得最优值γ时,必定满足JY)=1 即此优化问题等价于:ma(D,Ys.t.J/(Y)=1 上述优化问题是非线性、非光滑的,可以使用最速上升法求 解。当Y=Y时,定义正规锥N(Y)={aX:a≥0,X∈J(Y) 其中ω(·康表示函数J的次梯度。此时,优化问题的最速 上升方向为Wk=D一D,其中D为D在NY上的投影。 使用线性搜索方法确定步长大小 8k=arg max(D, (Y+8W)/J(Y+8W) 8≥0 °于是Y的更新过程为Yk+1=(Yk+8kW)J(Yk+8kW) 比算法具有更好的可扩展性,这是因为在每次迭 代过程中对偶方法不需要矩阵的完全奇异值分解。

...展开详情
试读 38P 矩阵低秩分解理论
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
  • 签到新秀

    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 分享宗师

    成功上传21个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
矩阵低秩分解理论 17积分/C币 立即下载
1/38
矩阵低秩分解理论第1页
矩阵低秩分解理论第2页
矩阵低秩分解理论第3页
矩阵低秩分解理论第4页
矩阵低秩分解理论第5页
矩阵低秩分解理论第6页
矩阵低秩分解理论第7页
矩阵低秩分解理论第8页

试读结束, 可继续读4页

17积分/C币 立即下载 >