1 WANG Hongyuan,et al:Efficient tracker based on sparse coding with Euclidean local structure-based constraint ·139. Table 1 Optimization for ELS constraint based SC(ELSSC) Input:Given N data points Y=[yY]ER,over-complete dictionary DR) Output:Sparse matrix C=[ce]R(x Parameters:Maxiumn iteration number J=10,neighborhood size K=5,all-zero vector co,a=0.01,B=0.5,y=0.001 1:For each point y,compute the nearest K neighborhoods N(y)and weights 2:Compute the SVD-decomposition of D UJVT,where VER()(2m) 3:compute ID'D‖，and set‖D'D|+2 B randomly 4:For i=1:N 5:For t=1:J 6:If lec)<,break inner iteration 7:0omie0=,6-,0=[Dy+290,-w+(y-28)c-DD,e-"],md0=VeR 8:Repesent”thparse colficient vector”,ie,optimize子l”-lke”tallo"l, 9:End 10:End Equation (5)is the objective function of our Eu- clidean local structure constraint-based SC and can be +7291a-ol-宁Ie-nl店 solved through iterative computation.In particular,at 1 lI3-6:D9〉+aIe0,-2pc9,-)+ the t-th iteration,for a single candidate y:in Y,Eq. (5)can be written as follows: 子"1-g-9e)+Y,81o+ 2 mineof(c()=min Iy:-De+ a ll e :+B lc)-0)(6) 〈De”,D〉-2ID,l3+BI-wI经= where.At the t-th iteration for the optimization of c,c,j is fixed.Therefore,we can 子1e"3-De）-29(c0,g-）- regard 1)as a constant.To solve Eq.(6),we intro- (y-2B)c.co+(Def Dco)+a llel+ duce the following surrogate function as presented in [11]: (兮%店+7291l+811》- 6o）=分1e-6l-71n0-l目 子Ic”-0+aI0,+R (7) (8) where is convex.According to Daubechies,when where AI-D'D is a strictly positive definite matrix,c,co) 1 =[D'y:+280+(y-28)c-D De-] 2 is strictly convex for any co with respect to c.Hence,in and our experiments,the constant A is set accordingly (A y-28;Table 1).Once the over-complete dictionary D is R=lxl+Y291o1-1l+ fixed,we can derive the following convex objective func- tion from Eq.(7): BIwI-子I” )lyDeare fixed at the t-th iteration.Thus,we can simplifyＴａｂｌｅ １ Ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ＥＬＳ ｃｏｎｓｔｒａｉｎｔ ｂａｓｅｄ ＳＣ（ＥＬＳＳＣ） Ｉｎｐｕｔ：Ｇｉｖｅｎ Ｎ ｄａｔａ ｐｏｉｎｔｓ Ｙ＝ ［ ｙ１… ｙＮ ］∈Ｒ ｍ×Ｎ ，ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ∈Ｒ ｍ×（ｎ＋２ｍ） Ｏｕｔｐｕｔ：Ｓｐａｒｓｅ ｍａｔｒｉｘ Ｃ＝ ［ｃ１… ｃＮ ］∈Ｒ （ｎ＋２ｍ）×Ｎ Ｐａｒａｍｅｔｅｒｓ： Ｍａｘｉｕｍｎ ｉｔｅｒａｔｉｏｎ ｎｕｍｂｅｒ Ｊ ＝ １０，ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｉｚｅ Ｋ＝ ５，ａｌｌ⁃ｚｅｒｏ ｖｅｃｔｏｒ ｃ０ ，α＝ ０．０１，β ＝ ０．５，γ ＝ ０．００１ １：Ｆｏｒ ｅａｃｈ ｐｏｉｎｔ ｙｉ，ｃｏｍｐｕｔｅ ｔｈｅ ｎｅａｒｅｓｔ Ｋ ｎｅｉｇｈｂｏｒｈｏｏｄｓ ＮＫ（ｙｉ） ａｎｄ ｗｅｉｇｈｔｓ ｗｊｉ ２：Ｃｏｍｐｕｔｅ ｔｈｅ ＳＶＤ⁃ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｏｆ Ｄ ＝ ＵΣＶ Ｔ ，ｗｈｅｒｅ Ｖ∈Ｒ （ｎ＋２ｍ）×（ｎ＋２ｍ） ３：ｃｏｍｐｕｔｅ ‖Ｄ ＴＤ‖， ａｎｄ ｓｅｔ‖Ｄ ＴＤ‖＋２β ｒａｎｄｏｍｌｙ ４：Ｆｏｒ ｉ ＝ １：Ｎ ５： Ｆｏｒ ｔ ＝ １：Ｊ ６： Ｉｆ ‖ｃ （ｔ） ｉ － ｃ （ｔ－１） ｉ ‖２ ＜ τ ， ｂｒｅａｋ ｉｎｎｅｒ ｉｔｅｒａｔｉｏｎ ７：Ｃｏｍｐｕｔｅ θ （ｔ） ｉ ＝ ∑ｊ ｗｊｉ ｃ （ｔ－１） ｊ ，ｖ （ｔ） ｉ ＝ １ γ ［Ｄ Ｔ ｙｉ ＋ ２βθｉ （ｔ－１） ＋ （γ － ２β）ｃｉ ｔ－１ － Ｄ ＴＤｉ ｃ ｔ－１ ］ ，ａｎｄ ｘ （ｔ） ｉ ＝Ｖｖ （ｔ） ｉ ∈Ｒ （ｎ＋２ｍ）×１ ８： Ｒｅｐｒｅｓｅｎｔ ｘ （ｔ） ｉ ｗｉｔｈ ｓｐａｒｓｅ ｃｏｅｆｆｉｃｉｅｎｔ ｖｅｃｔｏｒ ｃ （ｔ） ｉ ，ｉ．ｅ．，ｏｐｔｉｍｉｚｅ γ ２ ‖ｘ （ｔ） ｉ －Ｖｃ （ｔ） ｉ ‖２ ２ ＋α‖ｃ （ｔ） ｉ ‖１ ９： Ｅｎｄ １０：Ｅｎｄ Ｅｑｕａｔｉｏｎ （５） ｉｓ ｔｈｅ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎ ｏｆ ｏｕｒ Ｅｕ⁃ ｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ｃｏｎｓｔｒａｉｎｔ⁃ｂａｓｅｄ ＳＣ ａｎｄ ｃａｎ ｂｅ ｓｏｌｖｅｄ ｔｈｒｏｕｇｈ ｉｔｅｒａｔｉｖｅ ｃｏｍｐｕｔａｔｉｏｎ． Ｉｎ ｐａｒｔｉｃｕｌａｒ， ａｔ ｔｈｅ ｔ⁃ｔｈ ｉｔｅｒａｔｉｏｎ， ｆｏｒ ａ ｓｉｎｇｌｅ ｃａｎｄｉｄａｔｅ ｙｉ ｉｎ Ｙ， Ｅｑ． （５） ｃａｎ ｂｅ ｗｒｉｔｔｅｎ ａｓ ｆｏｌｌｏｗｓ： ｍｉｎｃｉ （ｔ） ｆ（ｃｉ （ｔ） ） ＝ ｍｉｎｃｉ （ｔ） ‖ｙｉ － Ｄｃｉ （ｔ）‖２ ２ ＋ α ‖ｃ （ｔ） ｉ ‖１ ＋ β ‖ｃ （ｔ） ｉ － θ （ｔ－１） ｉ ‖２ ２ （６） ｗｈｅｒｅ θ （ｔ） ｉ ＝ ∑ ｊｗｊｉ ｃ （ｔ－１） ｊ ． Ａｔ ｔｈｅ ｔ⁃ｔｈ ｉｔｅｒａｔｉｏｎ ｆｏｒ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｃｉ，ｃｊ，ｉ ≠ ｊ ｉｓ fiｘｅｄ． Ｔｈｅｒｅｆｏｒｅ， ｗｅ ｃａｎ ｒｅｇａｒｄ θ （ｔ－１） ｉ ａｓ ａ ｃｏｎｓｔａｎｔ． Ｔｏ ｓｏｌｖｅ Ｅｑ． （６）， ｗｅ ｉｎｔｒｏ⁃ ｄｕｃｅ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｓｕｒｒｏｇａｔｅ ｆｕｎｃｔｉｏｎ ａｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ［１１］： ψ（ｃｉ，ｃ０） ＝ λ ２ ‖ｃ （ｔ） ｉ － ｃ０‖２ ２ － １ ２ ‖Ｄｃ （ｔ） ｉ － Ｄｃ０‖２ ２ （７） ｗｈｅｒｅ λ ｉｓ ｃｏｎｖｅｘ． Ａｃｃｏｒｄｉｎｇ ｔｏ Ｄａｕｂｅｃｈｉｅｓ ［１３］ ， ｗｈｅｎ λＩ － Ｄ ＴＤ ｉｓ ａ ｓｔｒｉｃｔｌｙ ｐｏｓｉｔｉｖｅ ｄｅfiｎｉｔｅ ｍａｔｒｉｘ， ψ（ｃｉ，ｃ０） ｉｓ ｓｔｒｉｃｔｌｙ ｃｏｎｖｅｘ ｆｏｒ ａｎｙ ｃ０ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｃｉ ． Ｈｅｎｃｅ， ｉｎ ｏｕｒ ｅｘｐｅｒｉｍｅｎｔｓ， ｔｈｅ ｃｏｎｓｔａｎｔ λ ｉｓ ｓｅｔ ａｃｃｏｒｄｉｎｇｌｙ （ λ ＝ γ － ２β； Ｔａｂｌｅ １）． Ｏｎｃｅ ｔｈｅ ｏｖｅｒ⁃ｃｏｍｐｌｅｔｅ ｄｉｃｔｉｏｎａｒｙ Ｄ ｉｓ ｆｉｘｅｄ， ｗｅ ｃａｎ ｄｅｒｉｖｅ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｃｏｎｖｅｘ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃ⁃ ｔｉｏｎ ｆｒｏｍ Ｅｑ． （７）： ｆ（ｃ （ｔ） ｉ ） ＝ １ ２ ‖ｙｉ － Ｄｃ （ｔ） ｉ ‖２ ２ ＋ α ‖ｃ （ｔ） ｉ ‖１ ＋ β ‖ｃ （ｔ） ｉ － θ （ｔ－１） ｉ ‖２ ２ ＋ γ － ２β ２ ‖ｃ （ｔ） ｉ － ｃ０‖２ ２ － １ ２ ‖Ｄｃ （ｔ） ｉ － Ｄｃ０‖２ ２ ＝ １ ２ ‖ｙｉ‖２ ２ － 〈ｙｉ，Ｄｃ （ｔ） ｉ 〉 ＋ α ‖ｃ （ｔ） ｉ ‖１ － ２β〈ｃ （ｔ） ｉ ，θ （ｔ－１） ｉ 〉 ＋ γ ２ ‖ｃ （ｔ） ｉ ‖２ ２ － （γ － ２β）〈ｃ （ｔ） ｉ ，ｃ０〉 ＋ γ － ２β ２ ‖ｃ０‖２ ２ ＋ 〈Ｄｃ （ｔ） ｉ ，Ｄｃ０ 〉 － １ ２ ‖Ｄｃ０‖２ ２ ＋ β ‖θ （ｔ－１） ｉ ‖２ ２ ＝ γ ２ ‖ｃ （ｔ） ｉ ‖２ ２ － 〈ｙｉ，Ｄｃ （ｔ） ｉ 〉 － ２β〈ｃ （ｔ） ｉ ，θ （ｔ－１） ｉ 〉 － （γ － ２β）〈ｃ （ｔ） ｉ ，ｃ０〉 ＋ 〈Ｄｃ （ｔ） ｉ ，Ｄｃ０〉 ＋ α ‖ｃ （ｔ） ｉ ‖１ ＋ （ １ ２ ‖ｙｉ‖２ ２ ＋ γ － ２β ２ ‖ｃ０‖２ ２ ＋ β ‖θ （ｔ－１） ｉ ‖２ ２ ） ＝ γ ２ ‖ｃ （ｔ） ｉ － ｖ （ｔ） ｉ ‖２ ２ ＋ α ‖ｃ （ｔ） ｉ ‖１ ＋ Ｒ （８） ｗｈｅｒｅ ｖ （ｔ） ｉ ＝ １ γ Ｄ Ｔ ｙｉ ＋ ２βθ （ｔ－１） ｉ ＋ （γ － ２β）ｃ ｔ－１ ｉ － Ｄ ＴＤｃ ｔ－１ [ ] ａｎｄ Ｒ ＝ １ ２ ‖ｙｉ‖２ ２ ＋ γ － ２β ２ ‖ｃ０‖ － １ ２ ‖Ｄｃ０‖２ ２ ＋ β ‖θ （ｔ－１） ｉ ‖２ ２ － γ ２ ‖ｖ （ｔ） ｉ ‖２ ２ ａｒｅ fiｘｅｄ ａｔ ｔｈｅ ｔ⁃ｔｈ ｉｔｅｒａｔｉｏｎ． Ｔｈｕｓ， ｗｅ ｃａｎ ｓｉｍｐｌｉｆｙ 第 １ 期 ＷＡＮＧ Ｈｏｎｇｙｕａｎ， ｅｔ ａｌ： Ｅｆｆｉｃｉｅｎｔ ｔｒａｃｋｅｒ ｂａｓｅｄ ｏｎ ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ Ｅｕｃｌｉｄｅａｎ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ⁃ｂａｓｅｄ ｃｏｎｓｔｒａｉｎｔ ·１３９·