数学科学系

Department of Mathematical Sciences

Moving Convex Hulls for Sparse Recovery

报告题目:Moving Convex Hulls for Sparse Recovery

 

报告人:张振跃(浙江大学数学系)

 

时间:2013111(星期五)15:00-16:00

 

地点:理科楼数学系A404

 

摘要:A novel technique Moving Convex Hulls (MoCH) is proposed forsparse recovery in signal processing or compressive sensing with given noise level ε, based on a locally closed convex envelope of the signal cardinality function ||x||_0 in an ?_{\infty}-ball B(a, α) = {x : ||x−a||_{\infty} ≤ α}. As a basic step of the MoCH, the new model itself can produce a good approximation to the exact signal, and MoCH provides an iterative rule to improve the approximation. As the existing ?_1-norm based sparse models, there is a similar error bound for the solution of the new model to the ideal sparsest signal x0;". More importantly, there is an unbounded attracting domain G0 for a chosen in which the local convexifying can capture x0;" as the solution. We characterize G0 as three parts: an unbounded convex polyhedron without conditions on the coefficient matrix A, a convex polyhedron when x0;" is unique and a minimiser of residual over the ?_{\infty}-ball, and a set under conditions on the approximate orthogonality of columns of A and sparsity of x0;". Moreover, there is a sequence of disjointed subdomains {Gk} such that starting at a point in Gk, the MoCH can theoretically recover the sparsest signal within at most k moving steps. Two iterative algorithms, successive fixed-point iterations (SFPI) and an ADMM algorithm, are given for solving the local convexifying problem, and updating rules of the ball are discussed. The MoCH is compared with other existing algorithms on several simulation examples and four real-world data sets for sparse recovery in the applications like image recovery, face recognition, image deblurring, and hyperspectral unmixing.

 

联系人:贾仲孝