We consider the synthesis problem of Compressed Sensing: given $s$ and an $M\times n$ matrix $A$, extract from $A$ an $m\times n$ submatrix $A_m$, with $m$ as small as possible, which is $s$-good, that is, every signal $x$ with at most $s$ nonzero entries can be recovered from observation $A_m x$ by $\ell_1$ minimization: $x … Read more
The algebraic reformulation of the BMV conjecture is equivalent to a family of dimensionfree tracial inequalities involving positive semidefinite matrices. Sufficient conditions for these to hold in the form of algebraic identities involving polynomials in noncommuting variables have been given by Markus Schweighofer and the second author. Later the existence of these certificates has been … Read more
This paper reviews the Bregman methods, analyzes the linearized Bregman method, and proposes fast generalization of the latter for solving the basis pursuit and related problems. The analysis shows that the linearized Bregman method has the exact penalty property, namely, it converges to an exact solution of the basis pursuit problem if and only if … Read more
We address the inverse problem of designing isotropic pairwise particle interaction potentials that lead to the formation of a desired lattice when a system of particles is cooled. The design problem is motivated by the desire to produce materials with pre-specified structure and properties. We present a heuristic computation-free geometric method, as well as a … Read more
We consider optimization problems with polynomial inequality constraints in non-commuting variables. These non-commuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy … Read more
Image restoration models based on total variation (TV) have become popular since their introduction by Rudin, Osher, and Fatemi (ROF) in 1992. The dual formulation of this model has a quadratic objective with separable constraints, making projections onto the feasible set easy to compute. This paper proposes application of gradient projection (GP) algorithms to the … Read more
This work addresses the computation of free-energy di fferences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morph- ing procedure, we employ permutations of atoms; we transform atom n in the source conformation into atom \sigma(n) in the target conformation rather than directly transforming atom … Read more
We propose the DISCO algorithm for graph realization in $\real^d$, given sparse and noisy short-range inter-vertex distances as inputs. Our divide-and-conquer algorithm works as follows. When a group has a sufficiently small number of vertices, the basis step is to form a graph realization by solving a semidefinite program. The recursive step is to break … Read more
Given a power grid modeled by a network together with equations describing the power flows, power generation and consumption, and the laws of physics, the so-called N – k problem asks whether there exists a set of k or fewer arcs whose removal will cause the system to fail. We present theoretical results and computation … Read more
The integration to steady state of many initial value ODEs and PDEs using the forward Euler method can alternatively be considered as gradient descent for an associated minimization problem. Greedy algorithms such as steepest descent for determining the step size are as slow to reach steady state as is forward Euler integration with the best … Read more