Approximation accuracy, gradient methods, and error bound for structured convex optimization (Q607498)

The paper deals with the problem of accuracy estimation if optimization problems arising in practical applications are approximated by convex relaxations. Such relaxations are often highly structured and large scale. The author tries to answer the following two questions: (1) How accurate are approximations obtained via the convex relaxations; (2) How fast can the convex relaxations be solved? Examples from the area of compressed sensing and sensor network localization are considered. As an appropriate method for solving the structured and large scale relaxations the first-order gradient methods are proposed. An error bound on the distance to the solution set of the convex relaxation is derived for a class of regularized problems, and linear convergence of the gradient methods is investigated.