Beyond compressive sensing: sparse approximation algorithms for ill-condioned inverse problems – BECOSE

New algorithms. Inverse problems exploiting the sparse nature of the
solution rely on the minimization of the counting function, referred
to as the L0-«norm«. This problem being intractable in most practical
settings, many suboptimal resolutions have been suggested. The
proposal of algorithms dedicated to ill-conditioned inverse problems
will rely on nonconvex formulations using discrete or continuous
dictionaries. Proposing effective and efficient algorithms remains an
important challenge for problems of large dimension.

Theoretical analysis. The theoretical analysis aims at characterizing
the performance of heuristic sparse algorithms. The traditional
worst-case exact recovery guarantees are acknowledged to be rather
pessimistic because they may not reflect the average behavior of
algorithms. We propose to revisit some well-known greedy algorithms
and their theoretical conditions for exact reconstruction in the
context of continuous dictionaries. We also propose to improve the
worst-case understanding of standard greedy algorithms, and to
characterize their average beahvior.

From theory to practice. The proposed algorithms will be assessed in
the context of tomographic PIV. This flow measurement technique aims
to determine the 3D displacement of tracer particles that passively
follow the flow, based on the acquisition of a limited number of 2D
camera images. Presently available methods for 3D reconstruction and
flow tracking are still restricted to small volumes, which is the main
bottleneck together with accuracy and resolution limits. The sparse
approach is the key methodological tool to handle problems of larger
dimension. The proposed solutions will be validated using both
realistic simulators and real experimental data.

1. Proposal of new L0 minimization algorithms under non-negativity
constraints. In [Nguyen et al, Gretsi 2017], we proposed new greedy
algorithms that are improvements of the Non-Negative Orthogonal Matching
Pursuit (NNOMP) algorithm, using an efficient implementation based on the
active set algorithm for solving non-negative least squares subproblems.

2. Proposal of new safe screening techniques for variable selection,
formulated as L1 minimization (LASSO). These techniques aim to eliminate
variables from the optimization problem, while guaranteeing the optimality
of the LASSO solution [Herzet et Malti, ICASSP 2016].

3. Proposal of new exact recovery conditions of the support of a sparse
representation for the OMP and OLS algorithms [Herzet et al, IEEE TIT,
2016]. These conditions weaken the classical exact recovery conditions
based on mutual coherence in the case of sparse representations with
decaying coefficients. These are not only sufficient but also necessary
conditions for exact support recovery in the noise-free case.

4. Application of recent sparse reconstruction methods to the reconstruction
of a volume in tomographic PIV [Barbu et Herzet, MST 2016]. Volume
reconstruction is addressed under sparsity (number of seeded particles)
and non-negativity constraints. The 3D volume reconstruction is formulated
as a convex and non-differentiable optimization problem of large
dimension. This optimization problem is solved using the ADMM algorithm.

5. Organization of a special session «Compressed sensing and inversion« at
the Gretsi 2017 workshop (French workshop on signal and image
processing).

Workpackage 1 «Conception of new algorithms«. The short term
perspectives deal with the preparation of a journal paper which will
contain the algorithmic novelties related to L0 minimization under
non-negativity constraints.

Workpackage 2 «Theoretical analysis of algorithms«: the post-doctoral
student recruited at INRIA Rennes in October 2017 will work on
several axes of research:

- revisit some well-known greedy algorithms and their theoretical
conditions of exact reconstruction in the context of continuous
dictionaries.

- improve the worst-case understanding of standard greedy algorithms
and characterize their average behavior: what is their probability to
reconstruct the support of the sparse representation given the
distribution of the nonzero coefficients?


Workpackage 3 «From theory to practice«: the PhD student recruited at
ONERA in October 2017 will first evaluate the L0 minimization methods
in the context of tomographic PIV. Then, he will propose new screening
techniques (also called «pruning« in the tomographic PIV community)
aiming to reduce the dimension of the dictionary in sparse
approximation problems. The new screening techniques will extend the
scope of existing screening techniques from convex to non-convex
formulations.

International journal papers.

1. C. Herzet, Drémeau and C. Soussen, Relaxed recovery conditions for
OMP/OLS by exploiting both coherence and decay, IEEE Trans. Inf. Theory ,
vol. 62, no. 1, pp. 459-470, Jan. 2016.

2. I. Barbu and C. Herzet, A new approach for volume reconstruction in
TomoPIV with the alternating direction method of multipliers, Measurement
Science and Technology, vol. 27, no. 10, pp. 104002, Oct. 2016.

International conference.

1. C. Herzet and A. Malti, Safe screening tests for LASSO based on firmly non-
expansiveness, in Proc. IEEE ICASSP , Shanghai, Mar. 2016, pp.
4732-4736.

National conference.

1. T. T. Nguyen, C. Soussen, J. Idier and E.-H. Djermoune, An optimized
version of NNOMP, in Proc. Gretsi, Juan-les-Pins, France, Sep. 2017.

The past decade has witnessed a tremendous interest in the concept of sparse representations in signal and image processing. One of the main reasons explaining this enthusiasm stands in the discovery of compressive sensing, a new sampling paradigm defying the theoretical limits established sixty years before by Shannon. Compressive sensing led many researchers to focus on inverse problems involving fairly-well conditioned dictionaries as those arising from random, independent measurements. Yet in many applications, the dictionaries relating the observations to the sought sparse signal are deterministic and ill-conditioned. In these scenarios, many classical algorithms and theoretical analyses are likely to fail. The BECOSE project aims to extend the scope of sparsity techniques much beyond the academic setting of random and well-conditioned dictionaries.

1. Conception of new algorithms

Inverse problems exploiting the sparse nature of the solution rely on the minimization of the counting function, referred to as the L0-"norm". This problem being intractable in most practical settings, many suboptimal resolutions have been suggested. The conception of algorithms dedicated to ill-conditioned inverse problems will revolve around three lines of thought. First, we will step back from the popular L1-convexification of the sparse representation problem and consider more involved nonconvex formulations. Recent works indeed demonstrate their relevance for difficult inverse problems. However, designing effective and computationally efficient algorithms remains a challenge for problems of large dimension. Second, we will study the benefit of working with continuous dictionaries in contrast with the classical discrete approach. Third, we will investigate the exploitation of additional sources of structural information (on top of sparsity) such as non-negativity constraints.

2. Theoretical analysis of algorithms

The theoretical analysis aims at characterizing the performance of heuristic sparse algorithms. The traditional worst-case exact recovery guarantees are acknowledged to be rather pessimistic because they may not reflect the average behavior of algorithms. It is noticeable, though, that sharp worst-case exact recovery conditions are not even available for a number of popular L0 algorithms. We will focus on stepwise orthogonal greedy search algorithms, which are very well-suited to the ill-conditioned context. We foresee that they will enjoy much weaker recovery guarantees than simpler L0 algorithms. We further propose to elaborate an average analysis of greedy algorithms for deterministic dictionaries, which is a major open issue. To do so, several intermediate steps will be carried out including a guaranteed failure analysis and the derivation of weakened guarantees of success by taking into account other constraints on top of sparsity such as prior knowledge on the signs, coefficient values, and partial support information.

3. From theory to practice

The proposed algorithms will be assessed in the context of tomographic Particle Image Velocimetry (PIV), a rapidly growing imaging technique in fluid mechanics that will have strong impact in several industrial sectors including environment, automotive and aeronautical industries. This flow measurement technique aims to determine the 3D displacement of tracer particles that passively follow the flow, based on the acquisition of a limited number of 2D camera images. The resulting inverse problem involves high-dimensional data as a time sequence of highly resolved 3D volumes must be reconstructed. Presently available methods for 3D reconstruction and flow tracking are still restricted to small volumes, which is the main bottleneck together with accuracy and resolution limits. The sparse approach is the key methodological tool to handle problems of larger dimension. The proposed solutions will be validated using both realistic simulators and real experimental data.