We discuss an application of Stochastic Approximation to statistical estimation of high-dimensional sparse parameters. The proposed solution reduces to resolving a penalized stochastic optimization problem on each stage of a multistage algorithm; each problem being solved to a prescribed accuracy by the non-Euclidean Composite Stochastic Mirror Descent (CSMD) algorithm. Assuming that the problem objective is smooth and quadratically minorated and stochastic perturbations are sub-Gaussian, our analysis prescribes the method parameters which ensure fast convergence of the estimation error (the radius of a confidence ball of a given norm around the approximate solution). This convergence is linear during the first “preliminary” phase of the routine and is sublinear during the second “asymptotic” phase. We consider an application of the proposed approach to sparse Generalized Linear Regression problem. In this setting, we show that the proposed algorithm attains the optimal convergence of the estimation error under weak assumptions on the regressor distribution. We also present a numerical study illustrating the performance of the algorithm on high-dimensional simulation data.

We consider the problem of recovering a signal observed in Gaussian noise. If the set of signals is convex and compact, and can be specified beforehand, one can use classical linear estimators that achieve a risk within a constant factor of the minimax risk. However, when the set is unspecified, designing an estimator that is blind to the hidden structure of the signal remains a challenging problem. We propose a new family of estimators to recover signals observed in Gaussian noise. Instead of specifying the set where the signal lives, we assume the existence of a well-performing linear estimator. Proposed estimators enjoy exact oracle inequalities and can be efficiently computed through convex optimization. We present several numerical illustrations that show the potential of the approach.

We present a theoretical framework for adaptive estimation and prediction of signals of unknown structure in the presence of noise. The framework allows to address two intertwined challenges: (i) designing optimal statistical estimators; (ii) designing efficient numerical algorithms. In particular, we establish oracle inequalities for the performance of adaptive procedures, which rely upon convex optimization and thus can be efficiently implemented. As an application of the proposed approach, we consider denoising of harmonic oscillations.

We discuss two new methods of recovery of sparse signals from noisy observation based onℓ1-minimization. While they are closely related to the well-known techniques such as Lasso and Dantzig Selector, these estimators come with efficiently verifiable guaranties of performance. By optimizing these bounds with respect to the method parameters we are able to construct the estimators which possess better statistical properties than the commonly used ones. We link our performance estimations to the well known results of Compressive Sensing and justify our proposed approach with an oracle inequality which links the properties of the recovery algorithms and the best estimation performance when the signal support is known. We also show how the estimates can be computed using the Non-Euclidean Basis Pursuit algorithm.

Non-Gaussian component analysis (NGCA) introduced in offered a method for high-dimensional data analysis allowing for identifying a low-dimensional non-Gaussian component of the whole distribution in an iterative and structure adaptive way. An important step of the NGCA procedure is identification of the non-Gaussian subspace using principle component analysis (PCA) method. This article proposes a new approach to NGCA called sparse NGCA which replaces the PCA-based procedure with a new the algorithm we refer to as convex projection.

We consider the problem of constructing an aggregated estimator from a finite class of base functions which approximately minimizes a con- vex risk functional under the ℓ1 constraint. For this purpose, we propose a stochastic procedure, the mirror descent, which performs gradient de- scent in the dual space. The generated estimates are additionally aver- aged in a recursive fashion with specific weights. Mirror descent algo- rithms have been developed in different contexts and they are known to be particularly efficient in high dimensional problems. Moreover their implementation is adapted to the online setting. The main result of the paper is the upper bound on the convergence rate for the generalization error.

We study the problem of tracking a random walk observed with noise when the variance of the walk increment is unknown. We describe a sequence of estimators of the random walk and we design an algorithm to choose the best estimator among all the sequence. We give also a bound for the mean square error of this estimator. Finally some simulations are presented and we compare our algorithm with the Kalman filter when the variance of the walk increment is estimated.

Digital image analysis appears to be more and more relevant to the study of physical phenomena involving fluid motion, and of their evolution over time. In that context, 2D deformable motion analysis is one of the important issues to be investigated. The interpretation of such deformable 2D flow fields can generally be stated as the characterization of linear models provided that first order approximations are considered in an adequate neighborhood of so-called singular points, where the velocity becomes null. This paper describes an efficient method, based on a statistical approach, which explicitly addresses these problems, and allows us to locate, characterize and track such singular points in an image sequence. It does not require the prior computation of the velocity field. The method has been validated by experiments carried out with synthetic and real examples corresponding to meteorological image sequences. In fact, the described approach can be of interest in different applications dealing with the characterization of vector fields.

"Constructive wavelet networks" are investigated as a universal tool for function approximation. The parameters of such networks are obtained via some "direct" Monte Carlo procedures. Approximation bounds are given. Typically, it is shown that such networks with one layer of "wavelons" achieve an L(2) error of order O(N(-(rho/d))), where N is the number of nodes, d is the problem dimension and rho is the number of summable derivatives of the approximated function. An algorithm is also proposed to estimate this approximation based on noisy input-output data observed from the function under consideration. Unlike neural network training, this estimation procedure does not rely on stochastic gradient type techniques such as the celebrated "backpropagation" and it completely avoids the problem of poor convergence or undesirable local minima.