|
|
|
About the Maxwell Insitute Colloquia Albert Cohen Albert Cohen holds a Professorship at the Laboratoire Jacques-Louis Lions, Universite Paris VI. Prof. Cohen has made numerous lasting contributions to numerical analysis and signal processing including fundamental work on: multi-resolution wavelets, non-linear approximation, and numerical methods for partial differential equations. Prof. Cohen's current research focus is on the recent topic of sparse approximation. Specifically, Prof. Cohen and his collaborators have developed a framework for the analysis of optimal k-term approximation, and have made connections between sparse approximation and fundamental notions in high-dimensional geometry. Associated 1-Day Meeting: Saturday November 3, ICMS, India Street In connection with Professor Cohen's visit, researchers from across the UK who are interested in sparse approximation will meet on November 3rd at the International Centre for Mathemtical Sciences (ICMS) . Generous support for this event was supplied by the ICMS, Maxwell Institute, and the EPSRC funded Bridging the Gaps between engineering and mathematics Edinburgh research partnership. The schedule for the meeting is given below.
Abstracts: Albert Cohen, Near Optimal Recovery of Arbitrary Signals From Incomplete Measurements: Compressed sensing is a new concept in signal and image processing where one seeks to minimize the number of measurements to be taken from signals or images while still retaining the information necessary to approximate them well. The ideas have their origins in certain abstract results from functional analysis and approximation theory but? were recently brought into the forefront by the work of Candes-Romberg-Tao, and Donoho who constructed concrete algorithms and showed their promise in application. There remain several fundamental questions on both the theoretical and practical side of compressed sensing. This talk is primarily concerned about one of these issues revolving around just how well compressed sensing can approximate a given signal from a given budget of fixed linear measurements, as compared to adaptive linear measurements. More precisely, we consider discrete N-dimensional signals x with N >> 1, allocate n << N linear measurements of x, and we describe the range of k for which these measurements encode enough information to recover x to the accuracy of best k-term approximation. We also consider the problem of having such accuracy only with high probability. Mike Davies, Practical Algorithms for Sparse Approximation: I will talk about two recent innovations in calculating sparse approximations: gradient pursuits and iterative shrinkage. Gradient pursuits can be thought of as "nearly" orthogonal matching pursuit (OMP). The intuition is that the the orthogonalization at the nth step will nearly let you solve the orthogonalization ant the (n+1)th step. This can be achieved through an explicit line minimization along the steepest descent direction or using an approximate conjugate gradient update. Performance is similar to OMP while computational requirements and more in line with standard Matching Pursuit. Iterative thresholding is a relaxation algorithm. Many authors have proposed variations on iterative shrinkage. These can be derived using majorization minimization and can be applied to both convex and non-convex sparse approximation optimization. In the extreme case we can even have an iterative hard thresholding which directly minimizes the L0 cost function (locally). Arieh Iserles, Modified Fourier Expansions: Substantial effort has been expended in Cambridge lately looking into modified Fourier series, whereby the sine functions are shifted by half phase. This brings about substantially faster convergence for non-periodic functions and allows very rapid (faster than FFT) computation of expansion coefficients by quadrature methods for highly oscillatory integrals. We'll sketch briefly ongoing research, while highlighting open problems: Theoretical properties of modified Fourier expansions; Rapid evaluation of expansion coefficients; Generalization to Birkhoff series; Generalization to cubes, combined with polynomial subtraction and the hyperbolic cross; Generalization to planar domains with piecewise-linear boundaries; Applications to spectral calculations. Sofia C. Olhede, Inference for Frequency Domain Compressible Time Series: Seasonally Persistent Processes (SPPs) exhibit a power-law decay in the Fourier domain. This stochastic compression of the Fourier Transform (FT) even for stationary choices of the decay parameter leads to non-regular behaviour of the FT. The long-range dependence of the series in the time domain implies that inference in this domain will involve the inversion of highly non-sparse and very large matrices. Estimation for such processes is therefore non-trivial to implement. It is possible to derive the distribution of the FT evaluated at a parameter dependent choice of frequency grid. This distribution leads to the introduction a new likelihood function, conditional on the most compressible choice of basis for a posited compressibility of the time series. We discuss how to implement likelihood inference in this setting, the behaviour of the estimators, and large sample size approximations to their distribution. This is joint work with Emma McCoy (Imperial College London) and Dave Stephens (McGill) Mark D Plumbley, Geometry of Sparse Representations: In the the sparse representation problem, we would like to represent a given vector as a linear combination of basis vectors, using a representation with as few non-zero elements as possible. For example, we might wish to represent the spectrum of a frame of polyphonic music using a small number of "active" note spectra, representing notes. The minimum-1-norm relaxation of this problem, the Basis Pursuit (BP) or "Lasso" method, reduces to a linear program. However, there are also methods that sequentially construct approximate sparse representations, including matching pursuit (MP) or orthogonal matching pursuit (OMP). Recently it has emerged that the geometry of convex polytopes can give some interesting insight into these sparse represenation algorithms, and tell us about the conditions where (O)MP or BP find the true sparsest solution. This insight also lead to an algorithm, called "Polytope Faces Pursuit", that builds up a sparse solution like MP, but will find the 1-norm solution eventually. Laura Rebollo-Neira, Sparse Representations and Structured Noise Filtering: The role of sparse representations in the context of structured noise filtering will be discussed. Structured filtering is a particular problem of signal splitting, or signal separation, where the subspaces hosting the signal components are assumed to be known and complementary. Thus, the filtering can be realized in a straightforward manner by recourse to an oblique projection onto the subspace where one of the signals belongs, and along the subspace hosting the other components. This procedure allows us to separate the signals one by one. However, if the signal component subspaces are not well separated, the problem is of an ill-posed nature. Consequently, the numerical errors introduced by calculations being carried out in finite precision arithmetic may cause the failure to achieve the correct signal splitting. Our proposal for the numerical realization of the filtering is focussed on the search of a subspace where a class of signals is considered to lie. We assume that this class of signals is sparse in a given spanning set and devise an strategy aiming at finding such a subspace. Jared Tanner, Phase Transitions for l1 Regularization: The recovery of the sparsest solution of an underdetermined system of linear equations is in general NP hard. However, it is well known in numerous scientific disciplines that if one solves the l1 regularized least squares minimization then the sparsest solution can be recovered exactly, and in a stable fashion, provided there are sufficiently few non-zeros. Over the last three years this phase transition behavior has been fully characterized for random ortho-projectors. These results and some tempting generalization will be presented. This is joint work with David L. Donoho (Stanford). Links Maxwell Institute for Mathematical Sciences University of Edinburgh School of Mathematics |