The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Restricted Isometry Constants in Compressed Sensing | Network localization with some new wrinkles: Noncovex geometry in low dimension

Bubacarr Bah, Jesse Holzer, Graduate student in University of Edinburgh and graduate student in Math respectively

Date and Time: Nov 30, 2011 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


Bubacarr's talk:

Restricted Isometry Constants (RICs) of a matrix are a popular tool in the analysis of compressed sensing algorithms. The best known bounds will be presented for Gaussian matrices as well as expander graphs. In the former case we will also present explicit formulae for the bounds in three extreme asymptotic limits. Implications for compressed sensing will be discussed.

Jesse's talk

Given distances between nodes in Euclidean space, the network
localization problem is to estimate the positions of the nodes.
In other words, given a weighted graph G = (N,E,D),
find x_n in R^K, n in N, minimizing
sum_{n1n2 = e in E} (|x_n1 - x_n2| - d_e)^2. This is an
unconstrained minimization problem with a highly nonconvex

Network localization was the subject of the AIMMS/MOPTA modeling
competition this year, which I took part in together with UW-Madison
teammates Lisa Tang and Aditya Gore. In the competition, it was
given that node pairs (n1,n2) not in E are far apart. This
additional information should be used.

In this talk I'll discuss the difficult nonconvexity of the
network localization NLP, SDP relaxations for this problem,
our approach inspired by low-rank methods for SDP,
and how we dealt with node pairs not in E. As befits a talk of a
geometric nature, there will be lots of pretty pictures.