Ingrid Daubechies

The EMD algorithm, first proposed in [11], made more robust as well as more versatile in [12], is a technique that aims to decompose into their building blocks functions that are the superposition of a (reasonably) small number of components, well separated in the time-frequency plane, each of which can be viewed as approximately harmonic locally, with slowly varying amplitudes and frequencies. The EMD has already shown its usefulness in a wide range of applications including meteorology, structural stability analysis, medical studies -- see, e.g. [13]. On the other hand, the EMD algorithm contains heuristic and ad-hoc elements that make it hard to analyze mathematically. In this paper we describe a method that captures the flavor and philosophy of the EMD approach, albeit using a different approach in constructing the components. We introduce a precise mathematical definition for a class of functions that can be viewed as a superposition of a reasonably small number of approximately harmonic components, and we prove that our method does indeed succeed in decomposing arbitrary functions in this class. We provide several examples, for simulated as well as real data.

Under certain conditions (known as therestricted isometry property, or RIP) on them×Nmatrix Φ (wherem<N), vectorsx∈ ℝ^Nthat are sparse (i.e., have most of their entries equal to 0) can be recovered exactly fromy:= Φxeven though Φ⁻¹(y) is typically an (N−m)—dimensional hyperplane; in addition,xis then equal to the element in Φ⁻¹(y) of minimal 𝓁₁‐norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determiningx, as the limit of aniteratively reweighted least squares(IRLS) algorithm. The main step of this IRLS finds, for a given weight vectorw, the element in Φ⁻¹(y) with smallest 𝓁₂(w)‐norm. Ifx⁽ⁿ⁾is the solution at iteration stepn, then the new weightw⁽ⁿ⁾is defined byw:= [|x|²+ ε]^−1/2,i= 1, …,N, for a decreasing sequence of adaptively defined ε_n; this updated weight is then used to obtainx^{(n+ 1)}and the process is repeated. We prove that when Φ satisfies the RIP conditions, the sequencex⁽ⁿ⁾converges for ally, regardless of whether Φ⁻¹(y) contains a sparse vector. If there is a sparse vector in Φ⁻¹(y), then the limit is this sparse vector, and whenx⁽ⁿ⁾is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergencein the terminology of numerical optimization). The same algorithm with the “heavier” weightw= [|x|²+ ε]^−1+τ/2,i= 1, …,N, where 0 < τ < 1, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches aquadraticrate for τ approaching 0.

We consider the problem of portfolio selection within the classical Markowitz mean-variance framework, reformulated as a constrained least-squares regression problem. We propose to add to the objective function a penalty proportional to the sum of the absolute values of the portfolio weights. This penalty regularizes (stabilizes) the optimization problem, encourages sparse portfolios (i.e., portfolios with only few active positions), and allows accounting for transaction costs. Our approach recovers as special cases the no-short-positions portfolios, but does allow for short positions in limited number. We implement this methodology on two benchmark data sets constructed by Fama and French. Using only a modest amount of training data, we construct portfolios whose out-of-sample performance, as measured by Sharpe ratio, is consistently and significantly better than that of the naïve evenly weighted portfolio.

InfoMax and FastICA are the independent component analysis algorithms most used and apparently most effective for brain fMRI. We show that this is linked to their ability to handle effectively sparse components rather than independent components as such. The mathematical design of better analysis tools for brain fMRI should thus emphasize other mathematical characteristics than independence.

This paper proposes a novel Nyquist-rate analog-to-digital (A/D) conversion algorithm which achieves exponential accuracy in the bit-rate despite using imperfect components. The proposed algorithm is based on a robust implementation of a beta-encoder where the value of the base beta is equal to golden mean. It was previously shown that beta-encoders can be implemented in such a way that their exponential accuracy is robust against threshold offsets in the quantizer element. This paper extends this result by allowing for imperfect analog multipliers with imprecise gain values as well. A formal computational model for algorithmic encoders and a general test bed for evaluating their robustness is also proposed.

We analyze an Iteratively Re-weighted Least Squares (IRLS) algorithm for promoting l1-minimization in sparse and compressible vector recovery. We prove its convergence and we estimate its local rate. We show how the algorithm can be modified in order to promote lt-minimization for t<1, and how this modification produces superlinear rates of convergence.

We consider linear inverse problems where the solution is assumed to fulfill some general homogeneous convex constraint. We develop an algorithm that amounts to a projected Landweber iteration and that provides and iterative approach to the solution of this inverse problem. For relatively moderate assumptions on the constraint we can always prove weak convergence of the iterative scheme. In certain cases, i.e. for special families of convex constraints, weak convergence implies norm convergence. The presented approach covers a wide range of problems, e.g. Besov-- or BV--restoration for which we present also numerical experiments in the context of image processing.

We consider linear inverse problems where the solution is assumed to have a sparse expansion on an arbitrary preassigned orthonormal basis. We prove that replacing the usual quadratic regularizing penalties by weighted 𝓁^p‐penalties on the coefficients of such expansions, with 1 ≤p≤ 2, still regularizes the problem. Use of such 𝓁^p‐penalized problems withp< 2 is often advocated when one expects the underlying ideal noiseless solution to have a sparse expansion with respect to the basis under consideration. To compute the corresponding regularized solutions, we analyze an iterative algorithm that amounts to a Landweber iteration with thresholding (or nonlinear shrinkage) applied at each iteration step. We prove that this algorithm converges in norm.