Optimization Online


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

Amir Beck(becka***at***ie.technion.ac.il)
Marc Teboulle(teboulle***at***post.tau.ac.il)

Abstract: We introduce a class of nonconvex/affine feasibility problems, called (NCF), 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.

Keywords: 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

Category 1: Nonlinear Optimization

Citation: To be published in the book "Fixed-Point Algorithms for Inverse Problems in Science and Engineering", part of the Springer Verlag series Optimization and Its Applications

Download: [PDF]

Entry Submitted: 07/30/2010
Entry Accepted: 07/30/2010
Entry Last Modified: 07/30/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society