A Linearly Convergent Algorithm for Solving a Class of Nonconvex/Affine Feasibility Problems

被引：19

作者：

Beck, Amir ^{[1
]}

Teboulle, Marc ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Dept Ind Engn, IL-32000 Haifa, Israel

来源：

FIXED-POINT ALGORITHMS FOR INVERSE PROBLEMS IN SCIENCE AND ENGINEERING | 2011年 / 49卷

基金：

以色列科学基金会;

关键词：

Nonconvex affine feasibility; Inverse problems; Gradient projection algorithm; Linear rate of convergence; Scalable restricted isometry; Mutual coherence of a matrix; Sparse signal recovery; Compressive sensing; Affine rank minimization; UNCERTAINTY PRINCIPLES; SPARSE; RECONSTRUCTION; EQUATIONS; PROPERTY; SIGNALS;

D O I：

10.1007/978-1-4419-9569-8_3

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We introduce a class of nonconvex/affine feasibility (NCF) problems that consists of finding a point in the intersection of affine constraints with a nonconvex closed set. This class captures some interesting fundamental and NP hard problems arising in various application areas such as sparse recovery of signals and affine rank minimization that we briefly review. Exploiting the special structure of NCF, we present a simple gradient projection scheme which is proven to converge to a unique solution of NCF at a linear rate under a natural assumption explicitly given defined in terms of the problem's data.

引用

页码：33 / +

页数：2

共 23 条

[1]

[Anonymous], 1999, Athena scientific Belmont

[2]

[Anonymous], 2010, Convex optimization in signal processing and communications

[3] Projection algorithms for solving convex feasibility problems [J].

Bauschke, HH ;

Borwein, JM .

SIAM REVIEW, 1996, 38 (03) :367-426

[4] A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems [J].

Beck, Amir ;

Teboulle, Marc .

SIAM JOURNAL ON IMAGING SCIENCES, 2009, 2 (01) :183-202

[5] Iterative Thresholding for Sparse Approximations [J].

Blumensath, Thomas ;

Davies, Mike E. .

JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS, 2008, 14 (5-6) :629-654

[6] From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images [J].

Bruckstein, Alfred M. ;

Donoho, David L. ;

Elad, Michael .

SIAM REVIEW, 2009, 51 (01) :34-81

[7] SIGNAL ENHANCEMENT - A COMPOSITE PROPERTY MAPPING ALGORITHM [J].

CADZOW, JA .

IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1988, 36 (01) :49-62

[8] Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information [J].

Candès, EJ ;

Romberg, J ;

Tao, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (02) :489-509

[9] The restricted isometry property and its implications for compressed sensing [J].

Candes, Emmanuel J. .

COMPTES RENDUS MATHEMATIQUE, 2008, 346 (9-10) :589-592

[10] Exact reconstruction of sparse signals via nonconvex minimization [J].

Chartrand, Rick .

IEEE SIGNAL PROCESSING LETTERS, 2007, 14 (10) :707-710

← 1 2 3 →