Invited Session Thu.1.H 1028

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

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

Computable bounds for sparse recovery


Chair: Anatoli Juditsky



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

Alexandre d'Aspremont
High-dimensional geometry, sparse statistics and optimization


This talk will focus on a geometrical interpretation of recent results in high dimensional statistics and show how some key quantities controlling model selection performance can be approximated using convex relaxation techniques. We will also discuss the limits of performance of these methods and describe a few key open questions.



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

Fatma Kilinc Karzan
Verifiable sufficient conditions for l1-recovery of sparse signals

Coauthors: Anatoli Juditsky, Arkadi Nemirovski


In this talk, we will cover some of the recent developments in large-scale optimization motivated by the compressed sensing paradigm. The majority of results in compressed sensing theory rely on the ability to design/use sensing matrices with good recoverability properties, yet there is not much known in terms of how to verify them efficiently. This will be the focus of this talk. We will analyze the usual sparse recovery framework as well as the case when a priori information is given in the form of sign restrictions on the signal. We will propose necessary and sufficient conditions for a sensing matrix to allow for exact l1-recovery of sparse signals and utilize them. These conditions, although difficult to evaluate, lead to sufficient conditions that can be efficiently verified via linear or semidefinite programming. We will analyze the properties of these conditions while making connections to disjoint bilinear programming and introducing a new and efficient bounding schema for such programs. We will finish by presenting limits of performance of these conditions and numerical results.



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

Anatoli Juditsky
Accuracy guaranties and optimal l1-recovery of sparse signals

Coauthors: Fatma Kilinc-Karzan, Arkadi S. Nemirovski


We discuss new methods for recovery of sparse signals which are based on l1 minimization. Our emphasis is on verifiable conditions on the problem parameters (sensing matrix and sparsity structure) for accurate signal recovery from noisy observations. In particular, we show how the certificates underlying sufficient conditions of exact recovery in the case without noise are used to provide efficiently computable bounds for the recovery error in different models of imperfect observation. These bounds are then optimized with respect to the parameters of the recovery procedures to construct the estimators with improved statistical properties.
To justify the proposed approach we provide oracle inequalities which link the properties of the recovery algorithms to the best estimation performance in the Gaussian observation model.


  Payday Loans In Texas. In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.