We study the Sparse Plus Low-Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, … Read more
Euclidean Jordan algebras are the abstract foundation for symmetriccone optimization. Every element in a Euclidean Jordan algebra has a complete spectral decomposition analogous to the spectral decomposition of a real symmetric matrix into rank-one projections. The spectral decomposition in a Euclidean Jordan algebra stems from the likewise-analogous characteristic polynomial of its elements, whose degree is … Read more
The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit … Read more
We investigate geometric features of the unit ball corresponding to the sum of the nuclear norm of a matrix and the l_1 norm of its entries — a common penalty function encouraging joint low rank and high sparsity. As a byproduct of this effort, we develop a calculus (or algebra) of faces for general convex … Read more
Suppose we are given a matrix that is formed by adding an unknown sparse matrix to an unknown low-rank matrix. Our goal is to decompose the given matrix into its sparse and low-rank components. Such a problem arises in a number of applications in model and system identification, and is NP-hard in general. In this … Read more
Branching is an important component of branch-and-bound algorithms for solving mixed integer linear programs. We consider the problem of selecting, at each iteration of the branch-and-bound algorithm, a general branching disjunction of the form $“\pi x \leq \pi_0 \vee \pi x \geq \pi_0 + 1”$, where $\pi, \pi_0$ are integral. We show that the problem … Read more
We study the mixing inequalities which were introduced by Gunluk and Pochet (2001). We show that a mixing inequality which mixes n MIR inequalities has MIR rank at most n if it is a type I mixing inequality and at most n-1 if it is a type II mixing inequality. We also show that these … Read more