On October 27th-30th, 2008, IMA just hosted a Hot Topics Workshop entitled Multi-Manifold Data Modeling and Applications organized by Ron DeVore, Tamara Kolda, Gilad Lerman, and Guillermo Sapiro. All the abstracts are listed here. Some videos/posters are missing, however, I have made a list of the different talks/posters/presentations of interested to some of the subject covered here before. The videos are in the FLV format. The talks with the videos are listed first, the talks with the presentation's slides are listed afterwards. The remaining presentations with no material finish the list. All the videos of the workshop are listed at the end of this entry. I note that the Rice group is pushing the concept of manifold signal processing further with the new concept of Joint Manifold. I also note that the problem being solved by Ron DeVore bears some similarity with the Experimental Probabilistic Hypersurface (EPH) approach mentioned earlier. Finally, the talk of Ingrid Daubechies isn't about Analog to Digital conversion but rather about the solver used for solving a very interesting geophysics problem (the structure of the earth mantle) and a portfolio manangement problem where we learn that shorting is good! She also makes the remark that the RIP property should also be called that way because Rest In Peace is the peace of mind the property brings to the person who is using it (i.e. LP programming find the sparsest solution). The videos relevant to CS are in the CS Video section. With no further due, kick back, bring out the popcorn, relax, here we go:* Richard Baraniuk: Manifold models for signal acquisition, compression, and processing
Joint work with Mark Davenport, Marco Duarte, Chinmay Hegde, and Michael Wakin.
Compressive sensing is a new approach to data acquisition in which sparse or compressible signals are digitized for processing not via uniform sampling but via measurements using more general, even random, test functions. In contrast with conventional wisdom, the new theory asserts that one can combine "low-rate sampling" (dimensionality reduction) with an optimization-based reconstruction process for efficient and stable signal acquisition. While the growing compressive sensing literature has focused on sparse or compressible signal models, in this talk, we will explore the use of manifold signal models. We will show that for signals that lie on a smooth manifold, the number of measurements required for a stable representation is proportional to the dimensionality of the manifold, and only logarithmic in the ambient dimension — just as for sparse signals. As an application, we consider learning and inference from manifold-modeled data, such as detecting tumors in medical images, classifying the type of vehicle in airborne surveillance, or estimating the trajectory of an object in a video sequence. Specific techniques we will overview include compressive approaches to the matched filter (dubbed the "smashed filter"), intrinsic dimension estimation for point clouds, and manifold learning algorithms. We will also present a new approach based on the joint articulation manifold (JAM) for compressive distributed learning, estimation, and classification.
* Partha Niyogi : A Geometric perspective on machine Learning
The abstract reads:
Increasingly, we face machine learning problems in very high dimensional spaces. We proceed with the intuition that although natural data lives in very high dimensions, they have relatively few degrees of freedom. One way to formalize this intuition is to model the data as lying on or near a low dimensional manifold embedded in the high dimensional space. This point of view leads to a new class of algorithms that are "manifold motivated" and a new set of theoretical questions that surround their analysis. A central construction in these algorithms is a graph or simplicial complex that is data-derived and we will relate the geometry of these to the geometry of the underlying manifold. Applications to data analysis, machine learning, and numerical computation will be considered.
Large group discussion on What have we learned about manifold learning — what are its implications for machine learning and numerical analysis? What are open questions? What are successes? Where should we be optimistic and where should we be pessimistic?
* Ronald DeVore: Recovering sparsity in high dimensions
The abstract reads:
We assume that we are in $R^N$ with $N$ large. The first problem we consider is that there is a function $f$ defined on $Omega:=[0,1]^N$ which is a function of just $k$ of the coordinate variables: $f(x_1,dots,x_N)=g(x_{j_1},dots,x_{j_k})$ where $j_1,dots,j_k$ are not known to us. We want to approximate $f$ from some of its point values. We first assume that we are allowed to choose a collection of points in $Omega$ and ask for the values of $f$ at these points. We are interested in what error we can achieve in terms of the number of points when we assume some smoothness of $g$ in the form of Lipschitz or higher smoothness conditions.
We shall consider two settings: adaptive and non-adaptive. In the adaptive setting, we are allowed to ask for a value of $f$ and then on the basis of the answer we get we can ask for another value. In the non-adaptive setting, we must prescribe the $m$ points in advance.A second problem we shall consider is when $f$ is not necessarily only a function of $k$ variables but it can be approximated to some tolerance $epsilon$ by such a function. We seek again sets of points where the knowledge of the values of $f$ at such points will allow us to approximate $f$ well. Our main consideration is to derive results which are not severely effected by the size of $N$, i.e. are not victim of the curse of dimensionality. We shall see that this is possible.
Yi Ma : Dense error correction via L1 minimization
The abstract reads:
It is know that face images of different people lie on multiple low-dimensional subspaces. In this talk, we will show that these subspaces are tightly bundled together as a "bouquet". Precisely due to this unique structure, it allows extremely robust reconstruction and recognition of faces despite severe corruption or occlusion. We will show that if the image resolution and the size of the face database grow in proportion to infinity, computer can correctly and efficiently recover or recognize a face image with almost 100% of its pixels randomly and arbitrarily corrupted, a truly magic ability of L1-minimization.
[While the following abtract is listed, Ingrid Daubechies really talks about an Iterative thresholding solver used in a geophysics problem and a portfolio management problem. To have access to it, just click on the Video link.]. I am leaving the abstract as is as I would have liked to see that presentation as well.
The abstract reads:
In Analog-to-Digital conversion, continuously varying functions (e.g. the output of a microphone) are transformed into digital sequences from which one then hopes to be able to reconstruct a close approximation to the original function. The functions under consideration are typically band-limited (i.e. their Fourier transform is zero for frequencies higher than some given value, called the bandwidth); such functions are completely determined by samples taken at a rate determined by their bandwidth. These samples then have to be approximated by a finite binary representation. Surprisingly, in many practical applications one does not just replace each sample by a truncated binary expansion; for various technical reasons, it is more attractive to sample much more often and to replace each sample by just 1 or -1, chosen judicously.
In this talk, we shall see what the attractions are of this quantization scheme, and discuss several interesting mathematical questions suggested by this approach. This will be a review of work by many others as well as myself. It is also a case study of how continuous interaction with engineers helped to shape and change the problems as we tried to make them more precise.
* Mauro Maggioni : Harmonic and multiscale analysis on low-dimensional data sets in high-dimensions
The abstract reads:
We discuss recent advances in harmonic analysis ideas and algorithms for analyzing data sets in high-dimensional spaces which are assumed to have lower-dimensional geometric structure. They enable the analysis of both the geometry of the data and of functions on the data, and they can be broadly subdivided into local, global and multiscale techniques, roughly corresponding to PDE techniques, Fourier and wavelet analysis ideas in low-dimensional Euclidean signal processing. We discuss applications to machine learning tasks, image processing, and discuss current research directions.
* Mark Davenport: Joint manifold models for collaborative inference
The abstract reads:
We introduce a new framework for collaborative inference and efficient fusion of manifold-modeled data. We formulate the notion of a joint manifold model for signal ensembles, and using this framework we demonstrate the superior performance of joint processing techniques for a range of tasks including detection, classification, parameter estimation, and manifold learning. We then exploit recent results concerning random projections of low-dimensional manifolds to develop an efficient framework for distributed data fusion. As an example, we extend the smashed filter – a maximum likelihood, model-based estimation and classification algorithm that exploits random measurements – to a distributed setting. Bounds for the robustness of this scheme against measurement noise are derived. We demonstrate the utility of our framework in a variety of settings, including large scale camera networks, networks of acoustic sensors, and multi-modal sensors.
* Julien Mairal: Supervised dictionary learning
The abstract reads:
It is now well established that sparse signal models are well suited to restoration tasks and can effectively be learned from audio, image, and video data. Recent research has been aimed at learning discriminative sparse models instead of purely reconstructive ones. This work proposes a new step in that direction, with a novel sparse representation for signals belonging to different classes in terms of a shared dictionary and multiple class-decision functions. The linear variant of the proposed model admits a simple probabilistic interpretation, while its most general variant admits an interpretation in terms of kernels. An optimization framework for learning all the components of the proposed model is presented, along with experimental results on standard handwritten digit and texture classification tasks. This is a joint work with F. Bach (INRIA), J. Ponce (Ecole Normale Supérieure), G. Sapiro (University of Minnesota) and A. Zisserman (Oxford University).
* Chinmay Hegde : Random projections for manifold learning
The asbtract reads:
We propose a novel method for linear dimensionality reduction of manifold-modeled data. First, we show that given only a small number random projections of sample points in R^N belonging to an unknown K-dimensional Euclidean manifold, the intrinsic dimension (ID) of the sample set can be estimated to high accuracy. Second, we prove that using only this set of random projections, we can estimate the structure of the underlying manifold. In both cases, the number of random projections (M) required is linear in K and logarithmic in N, meaning that K less than M and M much less than N. To handle practical situations, we develop a greedy algorithm to estimate the smallest size of the projection space required to perform manifold learning. Our method is particularly relevant in distributed sensing systems and leads to significant potential savings in data acquisition, storage and transmission costs.Joint work with Michael Wakin and Richard Baraniuk.
* Marco F. Duarte: The smashed filter for compressive classification
The abstract reads:
We propose a framework for exploiting the same measurement techniques used in emerging compressive sensing systems in the new setting of compressive classification. The first part of the framework maps traditional maximum likelihood hypothesis testing into the compressive domain; we find that the number of measurements required for a given classification performance level does not depend on the sparsity or compressibility of the signal but only on the noise level. The second part of the framework applies the generalized maximum likelihood method to deal with unknown transformations such as the translation, scale, or viewing angle of a target object. Such a set of transformed signals forms a low-dimensional, nonlinear manifold in the high-dimensional image space. We exploit recent results that show that random projections of a smooth manifold result in a stable embedding of the manifold in the lower-dimensional space. Non-differential manifolds, prevalent in imaging applications, are handled through the use of multiscale random projections that perform implicit regularization. We find that the number of measurements required for a given classification performance level grows linearly in the dimensionality of the manifold but only logarithmically in the number of pixels/samples and image classes.This is joint work with Mark Davenport, Michael Wakin and Richard Baraniuk.
Ehsan Elhamifar : 3-D motion segmentation via robust subspace separation
The abstract reads:
We consider the problem of segmenting multiple rigid-body motions in a video sequence from tracked feature point trajectories. Using the affine camera model, this motion segmentation problem can be cast as the problem of segmenting samples drawn from a union of linear subspaces of dimension two, three or four. However, due to limitations of the tracker, occlusions and the presence of nonrigid objects in the scene, the obtained motion trajectories may contain grossly mistracked features, missing entries, or not correspond to any valid motion model.
In this poster, we present a combination of robust subspace separation schemes that can deal with all of these practical issues in a unified framework. For complete uncorrupted trajectories, we examine approaches that try to harness the subspace structure of the data either globally (Generalized PCA) or by minimizing a lossy coding length (Agglomerative Lossy Coding). For incomplete or corrupted trajectories, we develop methods based on PowerFactorization or L1-minimization. The former method fills in missing entries using a linear projection onto a low-dimensional space. The latter method draws strong connections between lossy compression, rank minimization, and sparse representation. We compare our approach to other methods on a database of 167 motion sequences with full motions, independent motions, degenerate motions, partially dependent motions, missing data, outliers, etc. Our results are on par with state-of-the-art results, and in many cases exceed them.
* Massimo Fornasier : Iteratively re-weighted least squares and vector valued data restoration from lower dimensional samples
The abstract reads:
We present the analysis of a superlinear convergent algorithm for L1-minimization based on an iterative reweighted least squares. We show improved performances in compressed sensing. A similar algorithm is then applied for the efficient solution of a system of singular PDEs for image recolorization in a relevant real-life problem of art restoration.
* Alvina Goh , René Vidal : Clustering on Riemannian manifolds
The abstract reads:
Over the past few years, various techniques have been developed for learning a low-dimensional representation of a nonlinear manifold embedded in a high-dimensional space. Unfortunately, most of these techniques are limited to the analysis of a single connected nonlinear submanifold of a Euclidean space and suffer from degeneracies when applied to linear manifolds (subspaces).
This work proposes a novel algorithm for clustering data sampled from multiple submanifolds of a Riemannian manifold. First, we learn a representation of the data using generalizations of local nonlinear dimensionality reduction algorithms from Euclidean to Riemannian spaces. Such generalizations exploit geometric properties of the Riemannian space, particularly its Riemannian metric. Then, assuming that the data points from different groups are separated, we show that the null space of a matrix built from the local representation gives the segmentation of the data. However, this method can fail when the data points are drawn from a union of linear manifolds, because M contains additional vectors in its null space. In this case, we propose an alternative method for computing M, which avoids the aforementioned degeneracies, thereby resulting in the correct segmentation. The final result is a simple linear algebraic algorithm for simultaneous nonlinear dimensionality reduction and clustering of data lying in multiple linear and nonlinear manifolds.We present several applications of our algorithm to computer vision problems such as texture clustering, segmentation of rigid body motions, segmentation of dynamic textures, segmentation of diffusion MRI. Our experiments show that our algorithm performs on par with state-of-the-art techniques that are specifically designed for such segmentation problems.
* Bradley K. Alpert : Compressive sampling reconstruction by subspace refinement
The abstract reads:
Spurred by recent progress in compressive sampling methods, we develop a new reconstruction algorithm for the Fourier problem of recovering from noisy samples a linear combination of unknown frequencies embedded in a very large dimensional ambient space. The approach differs from both L1-norm minimization and orthogonal matching pursuit (and its variants) in that no basis for the ambient space is chosen a priori. The result is improved computational complexity. We provide numerical examples that demonstrate the method's robustness and efficiency.Joint work with Yu Chen.
* Yoel Shkolnisky , Amit Singer : Structure determination of proteins using cryo-electron microscopy
The abstract reads:
The goal in Cryo-EM structure determination is to reconstruct 3D macromolecular structures from their noisy projections taken at unknown random orientations by an electron microscope. Resolving the Cryo-EM problem is of great scientific importance, as the method is applicable to essentially all macromolecules, as opposed to other existing methods such as crystallography. Since almost all large proteins have not yet been crystallized for 3D X-ray crystallography, Cryo-EM seems the most promising alternative, once its associated mathematical challenges are solved. We present an extremely efficient and robust solver for the Cryo-EM problem that successfully recovers the projection angles in a globally consistent manner. The simple algorithm combines ideas and principles from spectral graph theory, nonlinear dimensionality reduction, geometry and computed tomography. The heart of the algorithm is a unique construction of a sparse graph followed by a fast computation of its eigenvectors.Joint work with Ronald Coifman and Fred Sigworth.
* Yoel Shkolnisky , Amit Singer : High order consistency relations for classification and de-noising of Cryo-EM images
The abstract reads:
In order for biologists to exploit the full potential embodied in the Cryo-EM method, two major challenges must be overcome. The first challenge is the extremely low signal-to-noise ratio of the projection images. Improving the signal-to-noise by averaging same-view projections is an essential preprocessing step for all algorithms. The second challenge is the heterogeneity problem, in which the observed projections belong to two or more different molecules or different conformations. Traditional methods assume identical particles, therefore failing to distinguish the different particle species. This results in an inaccurate reconstruction of the molecular structure.
For the first problem, we present two different high order consistency relations between triplets of images. The inclusion of such high order information leads to improvement in the classification and the de-noising of the noisy images compared to existing methods that use only pairwise similarities. We also present a generalization of Laplacian eigenmaps to utilize such higher order affinities in a data set. This generalization is different from current tensor decomposition methods. For the second challenge, we describe a spectral method to establish two or more ab initio reconstructions from a single set of images. Joint work with Ronald Coifman and Fred Sigworth.
* Michael Wakin : Manifold models for single- and multi-signal recovery
The abstract reads:
The emerging theory of Compressive Sensing states that a signal obeying a sparse model can be reconstructed from a small number of random linear measurements. In this poster, we will explore manifold-based models as a generalization of sparse representations, and we will discuss the theory and applications for use of these models in single- and multi-signal recovery from compressive measurements.
* Allen Yang: High-dimensional multi-model estimation – its Algebra, statistics, and sparse representation
The abstract reads:
All the videos are listed below:Recent advances in information technologies have led to unprecedented large amounts of high-dimensional data from many emerging applications. The need for more advanced techniques to analyze such complex data calls for shifting research paradigms. In this presentation, I will overview and highlight several results in the area of estimation of mixture models in high-dimensional data spaces. Applications will be presented in problems such as motion segmentation, image segmentation, face recognition, and human action categorization. Through this presentation, I intend to emphasize the confluence of algebra and statistics that may lead to more advanced solutions in analyzing complex singular data structures such as mixture linear subspaces and nonlinear manifolds.
 | CPOPT: Optimization for fitting CANDECOMP/PARAFAC models October 30, 2008, Tamara G. Kolda (Sandia National Laboratories) |
| Mathematical problems suggested by Analog-to-Digital conversion October 30, 2008, Ingrid Daubechies (Princeton University) |
| Interpolation of functions on Rn October 29, 2008, Charles L. Fefferman (Princeton University) |
| Multi-manifold data modeling via spectral curvature clustering October 29, 2008, Gilad Lerman (University of Minnesota) |
| Visualization & matching for graphs and data October 29, 2008, Tony Jebara (Columbia University) |
| Topology and data October 29, 2008, Gunnar Carlsson (Stanford University) |
| Dense error correction via L1 minimization October 29, 2008, Yi Ma (University of Illinois at Urbana-Champaign) |
| Multilinear (tensor) manifold data modeling October 28, 2008, M. Alex O. Vasilescu (SUNY) |
| Recovering sparsity in high dimensions October 28, 2008, Ronald DeVore (Texas A & M University) |
| Clustering linear and nonlinear manifolds October 28, 2008, René Vidal (Johns Hopkins University) |
| Instance optimal adaptive regression in high dimensions October 28, 2008, Wolfgang Dahmen (RWTH Aachen) |
| Spectral and geometric methods in learning October 28, 2008, Mikhail Belkin (Ohio State University) |
| The best low-rank Tucker approximation of a tensor October 27, 2008, Lars Eldén (Linköping University) |
| A Geometric perspective on machine Learning October 27, 2008, Partha Niyogi (University of Chicago) |
| Detecting mixed dimensionality and density in noisy point clouds October 27, 2008, Gloria Haro Ortega (Universitat Politecnica de Catalunya) |
| Harmonic and multiscale analysis on low-dimensional data sets in high-dimensions October 27, 2008, Mauro Maggioni (Duke University) |
| Manifold models for signal acquisition, compression, and processing October 27, 2008, Richard G. Baraniuk (Rice University) |
No comments:
Post a Comment