Jon Lee

Victor K. Fuentes, Marcia Fampa, Jon Lee

Pseudoinverses are ubiquitous tools for handling over- and under-determined systems of equations. For computational efficiency, sparse pseudoinverses are desirable. Recently, sparse left and right pseudoinverses were introduced, using 1-norm minimization and linear programming. We introduce several new sparse pseudoinverses by developing linear and semi-definite programming relaxations of the well-known Moore-Penrose properties.

Gabriel Ponte, Marcia Fampa, Jon Lee

The maximum-entropy remote sampling problem (MERSP) is to select a subset of s random variables from a set of n random variables, so as to maximize the information concerning a set of target random variables that are not directly observable. We assume throughout that the set of all of these random variables follows a joint Gaussian distribution, and that we have the covariance matrix available. Finally, we measure information using Shannon's differential entropy. The main approach for exact solution of moderate-sized instances of MERSP has been branch-and-bound, and so previous work concentrated on upper bounds. Prior to our work, there were two upper-bounding methods for MERSP: the so-called NLP bound and the spectral bound, both introduced 25 years ago. We are able now to establish domination results between these two upper bounds. We propose an ``augmented NLP bound'' based on a subtle convex relaxation. We provide theoretical guarantees, giving sufficient conditions under which the augmented NLP bound strictly dominates the ordinary NLP bound. In addition, the augmented NLP formulation allows us to derive upper bounds for rank-deficient covariance matrices when they satisfy a technical condition. This is in contrast to the earlier work on the ordinary NLP bound that worked with only positive definite covariance matrices. Finally, we introduce a novel and very effective diagonal-scaling technique for MERSP, employing a positive vector of parameters. Numerical experiments on benchmark instances demonstrate the effectiveness of our approaches in advancing the state of the art for calculating upper bounds on MERSP.

Marcia Fampa, Jon Lee

We study sparse generalized inverses $H$ of a rank-$r$ real matrix $A$. We give a construction for reflexive generalized inverses having at most $r^2$ nonzeros. For $r=1$ and for $r=2$ with $A$ nonnegative, we demonstrate how to minimize the (vector) 1-norm over reflexive generalized inverses. For general $r$, we efficiently find reflexive generalized inverses with 1-norm within approximately a factor of $r^2$ of the minimum 1-norm generalized inverse.