Invited Session Mon.1.H 1028

Monday, 10:30 - 12:00 h, Room: H 1028

Cluster 21: Sparse optimization & compressed sensing [...]

New models and algorithms in sparse optimization


Chair: Benjamin Recht



Monday, 10:30 - 10:55 h, Room: H 1028, Talk 1

Nicolas Boumal
Riemannian algorithms and estimation bounds for synchronization of rotations

Coauthors: Pierre-Antoine Absil, Amit Singer


We estimate unknown rotation matrices Ri in SO(n) from a set of measurements of relative rotations Ri^{}RjT. Each measurement is either slightly noisy, or an outlier bearing no information. We study the case where most measurements are outliers. We propose a Maximum Likelihood Estimator (MLE) approach, explicitly acknowledging outliers in the noise model.
The MLE maximizes the log-likelihood function over the parameter space. That space is a product of rotation groups, possibly quotiented to account for invariance under a common rotation of the estimators.
To compute the MLE, we use Riemannian trust-region methods to maximize the log-likelihood function over the parameter space. That space is a matrix manifold, hence tools and analyses from (Absil et al., Optimization Algorithms on Matrix Manifolds, Princeton Univ. Press, 2008) apply gracefully.
We derive Riemannian Cramer-Rao bounds for synchronization, valid for a broad class of problem dimensions and noise distributions. These bounds admit a simple expression in terms of an information-weighted Laplacian of the measurement graph. Numerical tests suggest the MLE is asymptotically efficient in many cases.



Monday, 11:00 - 11:25 h, Room: H 1028, Talk 2

Mark A. Davenport
A simple framework for analog compressive sensing

Coauthor: Michael B. Wakin


Compressive sensing (CS) has recently emerged as a framework for efficiently capturing signals that are sparse or compressible in an appropriate basis. While often motivated as an alternative to Nyquist-rate sampling, there remains a gap between the discrete, finite-dimensional CS framework and the problem of acquiring a continuous-time signal. In this talk, I will describe a new approach to bridging this gap by exploiting the Discrete Prolate Spheroidal Sequences (DPSS's), a collection of functions that trace back to the seminal work by Slepian, Landau, and Pollack on the effects of time-limiting and bandlimiting operations. DPSS's form a highly efficient basis for sampled bandlimited functions; by modulating and merging DPSS bases, we obtain a dictionary that offers high-quality sparse approximations for most sampled multiband signals. This multiband modulated DPSS dictionary can be readily incorporated into the CS framework. I will provide theoretical guarantees and practical insight into the use of this dictionary for recovery of sampled multiband signals from compressive measurements.



Monday, 11:30 - 11:55 h, Room: H 1028, Talk 3

Benjamin Recht
Atomic norm denoising with applications to spectrum estimation and system identification

Coauthors: Badri N. Bhaskar, Parikshit Shah, Gonnguo Tang


One of the most common goals of data analysis is to reject noise by leveraging the latent structure present in the true signal. This talk will propose a general approach to such denoising problems by regularizing data fidelity with a penalty called the atomic norm. Atomic norm denoising is posed as a convex optimization problem and has generic, mean-squared-error guarantees. For sparse signals, atomic norm denoising is equivalent to soft-thresholding, but our techniques can be applied to estimate a variety of other objects and structures beyond sparse signals and images.
To demonstrate the wide applicability of atomic norm denoising, I will specialize the abstract formulation to two applications of practical interest. First, I will present a convex approach to superresolution, estimating the frequencies and phases of a mixture of complex exponentials. I will then apply the framework to identify linear dynamical systems from noisy, incomplete measurements. In both cases, atomic norm denoising efficiently achieves comparable or better error to existing heuristics without a priori knowledge of system parameters such as model order.


  online loans . But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.