lecture压缩感知与稀疏表示

机器学习与数据MachineLearningandData春模式识别与智能信息与通 网络搜索教中 邮电大内容提引压缩SRC/LRMC/RPCA(PCP)/MP/OMP/FS/ISTA/FISTA/ADMM/最优化问形式上的比比如:L1范数，核(Nuclear)本质上的凸(convex)优化问非凸(nonconvex)优化问L0-以L0范数为目标函若考虑 噪声，则min

y

221若考虑21min

y minmin0y贪婪(Greedy)匹配追踪(MatchingPursuit:正交匹配追踪(OrthogonalMatchingPursuit: 基本思想

每次迭代时，尝试确认出“最突出”的基算法步骤–2.jarg，加入下标集It–2.jarg，加入下标集It3.更新残差rt1rtrt,a1ia4若t=k则停止否则令tt+1,转第2步S.MallatandZ.Zhang:Matchingpursuitinatime-frequencydictionary,IEEESignalProc.,41(1993),pp. –2.–2.jarg 1i35.IIttc*argminyA2t yAc2t 基本思想算法步骤1令t=1，设置残差向量rtyIt6.若t=k,则停止;否则,令 Y.C.Pati,R.Rezaifar,andP.S. L1-把L0范数放松为L1范

Combinatorialmin0min0min0yyA22min1min1yyA22基追踪(BasisPursuit使用变 法转化为线性规划Programming)问求解LP问题的方法，比如单纯形(Simplex)法/内点法特征符号搜索(FeatureSignSearch:快速迭代收缩阈值算法1S.Chen,D.Donoho,andM.Saunders: positionbyBasisPursuit,SIAMReview,43,No.1,pp.129-159,2H.Lee,A.Battle,R.Raina,andAndrewY.Ng:EfficientSparseCodingAlgorithms,NIPS (Basis

min1

y令u

u0,v

1Tu1T

令zu;vv

B minmin1min1TzyBzzA–线性规划问题的算法：Simplexprimal-dualinterior-point/log-barrier…AS.Chen,D.Donoho,andM.Saunders: positionbyBasis,L12考虑一个特殊的L1-最小化问题2x +x

xc其最优解为

x*T

cj, cj–其 x*Tc

cjc

jifcjSoft-Thresholding(FeatureSignFeatureSignSearch考虑下述L1最小化问argminAxy2+ Axyx注意到问题的最优性条件x

2+ 11 Axy+sign jAx2 如果x的分量的符号已知，则L1范数可被化简，相应的子问化为无约束二次规划(QP)•LFeatureSignSearch•L tiveShrinkageThresholding

min + 1考虑L-最小化问1x

Ax

x2

Axc2在xk处，对f(x)进行2 级数展开,其中L为Lipschitz常数2fxQx,xfxxx,fxLx xk1argmin +Qx,xk argmin + x 1fx 2ISTA算法令k=0，初始化x0;若不满足收敛条件,计算xk+1,并令FastI tiveShrinkageThresholdingAlgorithm考虑

-最小化

min

+f 初始化:ykxk-1，tk=1,在yk处，对f(x)进行2 级数展开,其中L为Lipschitz常数fxQx,yfyxy,fyLx 2 2

2则 argmin +Lx 1fy kkk 11kkk

kyk1xk+tk1xkk

/FISTAFISTA算法初始化x0ykxk-1tk=1k=1[1]Beck,A;Teboulle,M(2009)."Afasttiveshrinkage-thresholdingalgorithmforlinear2Q/AnyQuestion?F矩阵的最佳低秩近似问题FD

DX

rankDposition:SVD)，得出:

r其中Srdiag1,2,...,r,12r矩阵填充问题minrankDs.t.PDPXDD*放松为D*D

s.t.PDPX奇异值阈值化(SingularValueThresholding:[1]J.-F.Cai,E.J.Cand´es,Z.Shen:Asingularvaluethresholdingalgorithmfor最优化问

min +1DX 其中*表示矩阵的核(Nuclear)范数,等于D的奇异值的2其最2D*argminD

+

D

F

其中[U,S,V 为矩阵X的奇异值分解(SVD:SingularValue position) 表示对矩阵对角线上的元素进行SoftThresholding处理[1]J.-F.Cai,E.J.Cand´es,Z.Shen:Asingularvaluethresholdingalgorithmfor DSRC问题SSC问题

D,x

x1x1

1 yAx1C1E1G C1E1GC,E

XXCEG,

diagCLRR问题 XXZZ,

增 日乘子AugmentedLagrangeMultiplier:乘子的交替方AlternatingDirectionMethodof1DimitriP.Bertsekas:ConstrainedOptimizationandLagrangeMultiplie2S.Boyd,etal.:DistributedOptimizationandStatisticalLearningviatheMethodofMultipliers,FTML2010.3Lin,Chen,Wu,andMa,“TheAugmentedLagrangeMultiplierMethodrMethods,AlternatingorExactRecovery增 日乘子法建 日辅助函

minfxs.t.AxxL0x,建立增 日辅助函

xTAxbLx,fx

Axb222

Axb 日乘子法(AugmentedLagrangexk1argminLx,kxk1kAxk1ma也叫乘子法(MethodofmaMethods,ADMM:AlternatingADMM:AlternatingDirectionMethodofminfxgzs.t.AxBz 2Lx,z,2

xgz

AxBzc2

AxBzcxk1argminLxk1argminLx,zk1,kxzk1argminLxk1,z,kk1zAxk1Bzk1乘子法(MM:Methodofxk1,zk1argminLx,z,kk1Axk1Bzk11ZhouchenLinetal.,FastConvexOptimizationAlgorithmsforExactRecoveryofaCorruptedLow-RankMatrix,TechnicalReport,UIUC,August2009. MethodofMultipliers,FTMLALMADMM1考虑下述L1最小化问argmin1Axb2 该问题等价为下述有约束L1最小化问argmin1Ayb2

y x1 x1Lx,y,

Ayb22

yx,yx22–求解上述无约束优化ALMADMM1求解无约束优化Lx,y,

Ayb22

yx,x x

yx2–交替求解下列子优化问题,直到收敛2

argminLx,y,Ay

Primalupdating:2 yx,yx

argargmaxLx,y,yx,DualALMADMM1求解无约束优化Lx,y,

Ayb22

yx,x x

yx2–交替求解下列容易求解的子问题,直到收敛2Primalupdating:argminLx,y,y

Ay

2yx,

yx2argmaxLx,y,yx,2

Dual argargminLx,y, yx,yxx122ALMADMM1求解无约束优化Lx,y,

Ayb22

yx,x x

yxk kkkkDual2–交替求解下列容易求解的子问题,直到收敛22argminA2argminAyb2yx,yx21xargmin xy/22y22y/ kk/y22y22ATAI1ATbxALMADMM2考虑矩阵填充DD

s.t.PDPXD–构造增广 日辅助函D2FLD,2F

,PDX*2*

D–保留与D有关的项，记为g(D)，对g(D)在Dk处进行级数展gD ,PDXPDX

*2 gDkgDk,D *22

D gDkPkPDkX1ALMADMM2通过求解h(D)来更新 argminhD gDgD,D D k

DDkargminhD1 1DDgDD*2kk2Fk Pkk kXDual–交替求解下列容易求解的子问题,直到收敛Primalupdating:SVT1/DkgDk/Q/AnyQuestion?压缩感知的简理 精稀疏编EmmanuelCandèsandTerenceTao,"Decodingbylinear4203-4215,December2005EmmanuelCandès,JustinRomberg,andTerenceTao,"Robustuncertaintyprinciples:Exactsignalreconstructionfromhighly52(2)pp.489-509,Feb.2006.矩阵填(2008)717- E.Candès,T.Tao,Thepowerofrelaxation:Near-optimalmatrix优化算

S.Boyd,etal.:DistributedOptimizationandStatisticalLearningviatheAlternatingDirectionMethodofMultipliers,FoundationandTrendsinMachineLearning,Vol.3,No.1,pp.1-122,2010.NealParikhandStephenBoyd:ProximalAlgorithms,FoundationsandTrendsinOptimization,Vol.1,No.3,pp.1-108,2013.压缩感知与稀疏表示MichaelElad:SparseandRedundantRepresentations:TheorytoAp