EURASIP Tutorial 1

The goal of this tutorial is to present in simple and insightful geometric arguments, a recent family of algorithms that build around the elegant notion of projections onto convex sets.  Instead of trying to minimize a single loss function, over the given set of training data, a different path is employed.  Measurements are received sequentially in time, and each measurement point defines a region in which the solution lies, with high probability.  Hence, the main goal of this methodology is the most natural one; that is, to locate a point in the intersection of all these data-defined convex regions. The tool which is employed is that of projections, hence all algorithms exhibit linear computational dependence, on the number of parameters to be estimated. After all, projections are inner products. 

The way the theory is developed allows for a single recursion to describe the most general formulation of classification as well as regression tasks.  All is needed, each time the problem changes, is to modify accordingly the respective projection operator, which is involved in the updating recursion.  Moreover, if convex constraints are present, all is needed is to perform an extra projection per time recursion, for each one of the available constraints, hence retaining the linear dependence of the computations on the number of free parameters. Finally, since only inner products are involved, the methodology lends readily itself for operations in Reproducing kernel Hilbert spaces (RKHS) , hence it offers itself for treating nonlinear tasks.

The way this tutorial will evolve is to present the different “faces”,  that the updating recursion takes, in the context of specific applications:

Ø  The unconstrained task will be demonstrated in the context of classification as well as channel estimation/equalization.  For each one of the problems, one has to “learn” to build the appropriate convex region that defines the set of possible solutions.

Ø  The constrained case will be demonstrated in the context of robust beamforming, where not only linear but also more complex constraints for robust beamforming will be presented.

Ø  Sparsity-aware learning, in the context of compressive sensing, will then be discussed. This is also a constrained problem, where the constraint is typically the l₁ norm. However, by exploiting the potential of our methodology, we will see that other alternatives, to the l₁ norm, can also be accommodated, which are more appropriate for adaptive learning.  The computation dependence still remains linear.

Ø  Finally, the notion of RKHS will be presented and the potential of our methodology to operate in such spaces, in order to tackle elegantly nonlinear tasks, will be discussed.  Still, working in such high dimensional spaces will be guided by the single recursive equation, as mentioned before. The projection operator will be adjusted to account for the new space, in which the activity takes place. Computational linear dependence is not affected.

Although, the theory is associated with strong convergence results, that have been developed for each one of the cases mentioned before, we will not delve in such mathematical details. The goal is to present the algorithmic family around its main concepts, using MATLAB examples for each one of the cases, in order to demonstrate how to play with the involved ‘trimming” parameters. The MATLAB code will be given to the participants.

Reference

S. Theodoridis, K. Slavakis, I. Yamada “Adaptive Learning in a World of Projections”, IEEE Signal Processing Magazine, Vol.28(1),  pp. 97-123, January 2011.

Download Link