ABSTRACT:
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
ABSTRACT:
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 objective.
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.
Discovery Building, Orchard View Room
Bubacarr Bah, Jesse Holzer