Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems

Many problems in signal processing and statistical inference involve finding sparse solutions to under-determined, or ill-conditioned, linear systems of equations. A standard approach consists in minimizing an objective function which includes a quadratic (squared $\ell_2$) error term combined with a sparseness-inducing ($\ell_1$) regularization term.{\it Basis pursuit}, the {\it least absolute shrinkage and selection operator} (LASSO), … Read more

Smooth Optimization Approach for Covariance Selection

In this paper we study a smooth optimization approach for solving a class of non-smooth {\it strongly} concave maximization problems. In particular, we apply Nesterov’s smooth optimization technique \cite{Nest83-1,Nest05-1} to their dual counterparts that are smooth convex problems. It is shown that the resulting approach has $\cO(1/{\sqrt{\epsilon}})$ iteration complexity for finding an $\epsilon$-optimal solution to … Read more

In pursuit of a root

The basis pursuit technique is used to find a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise fits the least-squares problem only approximately, and a single parameter determines a curve that traces the trade-off between the least-squares fit and the one-norm of the solution. We show that the function that describes this … Read more

Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, … Read more

Explicit reformulations for robust optimization problems with general uncertainty sets

We consider a rather general class of mathematical programming problems with data uncertainty, where the uncertainty set is represented by a system of convex inequalities. We prove that the robust counterparts of this class of problems can be equivalently reformulated as finite and explicit optimization problems. Moreover, we develop simplified reformulations for problems with uncertainty … Read more

Symmetry in semidefinite programs

This paper is a tutorial in a general and explicit procedure to simplify semidefinite programming problems which are invariant under the action of a group. The procedure is based on basic notions of representation theory of finite groups. As an example we derive the block diagonalization of the Terwilliger algebra in this framework. Here its … Read more

Column basis reduction and decomposable knapsack problems

We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b’   ≤   Ax   ≤   b,   x ∈ Zn with b’   ≤   (AU)y   ≤   b,   y ∈ Zn, where U is a unimodular matrix computed via basis reduction, to make the … Read more

An O(n^2) Algorithm for Lot Sizing with Inventory Bounds and Fixed Costs

Lot-sizing problems with inventory bounds and fixed charges have not received much attention in the literature, even though there are many emerging applications in which highly specialized storage is the main activity of interest. The traditional infinite capacity and variable cost assumptions on inventory that have been prevalent in the literature are inappropriate in situations … Read more

Partition Inequalities for Capacitated Survivable Network Design Based on Directed P-Cycles

We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the … Read more

The Flow Set with Partial Order

The flow set with partial order is a mixed-integer set described by a budget on total flow and a partial order on the arcs that may carry positive flow. This set is a common substructure of resource allocation and scheduling problems with precedence constraints and robust network flow problems under demand/capacity uncertainty. We give a … Read more