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

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.

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

Article

Download

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