Periodic nonuniform sampling is a known method to sample spectrally sparse signals below the Nyquist rate. This strategy relies on the implicit assumption that the individual samplers are exposed to the entire frequency range. This assumption becomes impractical for wideband sparse signals. The current paper proposes an alternative sampling stage that does not require a full-band front end. Instead, signals are captured with an analog front end that consists of a bank of multipliers and lowpass filters whose cutoff is much lower than the Nyquist rate. The problem of recovering the original signal from the low-rate samples can be studied within the framework of compressive sampling. An appropriate parameter selection ensures that the samples uniquely determine the analog input. Moreover, the analog input can be stably reconstructed with digital algorithms. Numerical experiments support the theoretical analysis.
It may be a good scheme for the Arduino,wink, wink :-)
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
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?
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
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.
This is joint work with John Wright of UIUC.
[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.
* Ingrid Daubechies: Mathematical problems suggested by Analog-to-Digital conversion
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
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
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.
This is joint work with Richard Baraniuk, Marco Duarte, and Chinmay Hegde.
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).
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
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.
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.
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:
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.
To the untrained eye, it may look like I am generating a new page every week. It may well be the case. In order to give a better bird's eye view of the current pages I have created on the subject, I have mindmapped all these pages using mind42.com (see map below). The same schematic with attendant links is also available in a Freedmind format here.
The first episode of the Saturday Morning Cartoon has already been viewed 193 times. This week's Saturday Morning Cartoon had to be cut in three parts. Most of the in-depth material can be found on the Compressive Sensing Hardware page.
Part 1
Part 2
Part 3
The scenario can be found here. The Saturday Morning Cartoon series can be found here.
The aim of antenna array synthesis is to achieve a desired radiation pattern with the minimum number of antenna elements. In this paper the antenna synthesis problem is studied from a totally new perspective. One of the key principles of compressive sensing is that the signal to be sensed should be sparse or compressible. This coincides with the requirement of minimum number of element in the antenna array synthesis problem. In this paper the antenna element of the array can be efficiently reduced via compressive sensing, which shows a great improvement to the existing antenna synthesis method. Moreover, the desired radiation pattern can be achieved in a very computation time which is even shorter than the existing method. Numerical examples are presented to show the high efficiency of the proposed method.
We consider the problem of recovering a matrix from its action on a known vector in the setting where the matrix can be represented efficiently in a known matrix dictionary. Connections with sparse signal recovery allows for the use of efficient reconstruction techniques such as Basis Pursuit. Of particular interest is the dictionary of time-frequency shift matrices and its role for channel estimation and identification in communications engineering. We present recovery results for Basis Pursuit with the time-frequency shift dictionary and various dictionaries of random matrices.
Petros Boufounos has made available the presentations he has made so far on the subject of CS:
Boufounos P., "Compressive Sensing and Beyond: New approaches to signal acquisition and processing." Variations presented at: - Mitsubishi Electric Research Laboratories, May 19, 2008, Boston, MA - Electrical Engineering Departmental Seminar, Princeton University, April 14, 2008, Princeton, NJ. - Center for Signal and Image Processing Seminar, Georgia Institute of Technology, March 17, 2008. - Electrical Engineering Seminar, Columbia University, February 19, 2008, New York, NY.
Boufounos P., Baraniuk R. G. "1-Bit Compressive Sensing." 42nd annual Conference on Information Sciences and Systems (CISS) 2008, March 19-21 2008, Princeton, NJ.
I also note that Albert Cohen has made most of his papers available on his site. Kudos to him.
On a different note, John Hawks reflects on the recent publication of two people's genome in Nature and finishes his entry with:
In the meantime, of course population genomics is what we're all about here in the Hawks lab. Single-locus genetics has gone the way of the dodo. Er...I suppose if you study dodos, you'd better go whole-genome with them, too. My only question: exactly how much hard drive space am I expected to have, if I'm going to deal with 100,000 genomes?
How about random projections ?
Finally, I am told by some readers that the following websites are not reachable in some parts of the world:
Very recently, blogger.com and therefore this blog were not available in Turkey for a while. I had a similar problem a while back because I sometimes use an ISP with a weird sounding name and some sites are blocking it by default. The only ways around that problem are:
to complain to the site owner (but in my case, I have no power on either blogger nor googlepages)
use a different ISP, or
use anonymous proxies like the one mentioned in the Tor Project.
If you continue on having problems reaching these pages, please let me know.
I was wondering when this subject would come up. Out of the many indirect sensing schemes, diffraction is a sensing scheme that most everybody has heard about. It is a lensless imaging process that requires a computational step to obtain an image.
On top of it, one can use a high luminosity source, as high as the sample allows. Stefano Marchesini has written on the subject with a particular view on how Compressive sensing could be used to alleviate some of the very large sampling required by the current direct methods. In some of the approaches, there is some consideration for using coded apertures.
The Fourier inversion of coherent diffraction patterns offers diffraction-limited three dimensional images without the aberrations, inefficiencies and depth-of field limitations of lens-based tomographic systems. We report experimental images inverted using holographic and computational phase retrieval methods. Ultimately the resolution of X-ray diffraction imaging will be limited by radiation damage. This limit can be overcome using pulses faster than the damage process. The first experimental verification of the principle of flash diffraction imaging using a soft X-ray free-electron laser will be presented. Experiments aimed at the characterization of the dynamics of organic matter under intense radiation and validation of theoretical models will be discussed.
Any object on earth has two fundamental properties: it is finite, and it is made of atoms. Structural information about an object can be obtained from diffraction amplitude measurements that account for either one of these traits. Nyquist-sampling of the Fourier amplitudes is sufficient to image single particles of finite size at any resolution. Atomic resolution data is routinely used to image molecules replicated in a crystal structure. Here we report an algorithm that requires neither information, but uses the fact that an image of a natural object is compressible. Intended applications include tomographic diffractive imaging, crystallography, powder diffraction, small angle x-ray scattering and random Fourier amplitude measurements.
This is novel and interesting. Instead of using only a CS encoding / measurement matrix that is Gaussian or else, this new approach uses both multiplexed measurements and "normal" samples and show that after some subsampling, one can recover the full original signal.
In this paper, the theoretical analysis of compressive sensing via random filter, firstly outlined by J. Romberg [compressive sensing by random convolution, submitted to SIAM Journal on Imaging Science on July 9, 2008], has been refined or generalized to the design of general random filter used for compressive sensing. This universal CS measurement consists of two parts: one is from the convolution of unknown signal with a random waveform followed by random time-domain subsampling; the other is from the directly time-domain subsampling of the unknown signal. It has been shown that the proposed approach is a universally efficient data acquisition strategy, which means that the n-dimensional signal which is S sparse in any sparse representation can be exactly recovered from Slogn measurements with overwhelming probability.
I note that most of the papers that are providing a rationale for this paper are still in preprint and have shown up on Arxiv only about a month ago. I realize that one of the author reads this blog, but I still find it amazing how the web is enabling some thought process acceleration. On a technical level, I note that this approach bears some similarity to Dense Error Correction via l1 Minimization, John Wright and Yi Ma, except that the location of the identity matrix in the traditional Measurement matrix is different and this has profound implication on the measurement process ( whereas it doesn't in the paper by John Wright and Yi Ma ). If one were to mix both approaches, one could conceivably subsample non-sparse signals! I can think of different ways to use the concepts in this paper in imaging.
We consider the problem of sparse signal recovery from a small number of random projections (measurements). This is a well known NP-hard to solve combinatorial optimization problem. A frequently used approach is based on greedy iterative procedures, such as the Matching Pursuit (MP) algorithm. Here, we discuss a fast GPU implementation of the MP algorithm, based on the recently released NVIDIA CUDA API and CUBLAS library. The results show that the GPU version is substantially faster (up to 31 times) than the highly optimized CPU version based on CBLAS (GNU Scientific Library).
There is now a video of Richard Baraniuk showing his latest introduction to Compressed Sensing at Microsoft Research on August 4, 2008. Please be aware, that the address does not seem to work with Firefox, Chrome or Opera (I tried), it only works with Internet Explorer. The original link that can be seen from any browser is here. It eventually yields the IE only presentation.
The presentation is getting better and better, or I am just rediscovering new points everytime I see it. In the matched filter sequence, Rich reminds us that the random projection classification work with a nearest neighbor concept (since we are using an embedding projection). I just read a new paper on NN and SVM classifier entitled: In Defense of Nearest-Neighbor Based Image Classification by Oren Boiman, Eli Shechtman and Michal Irani. The abstract reads:
State-of-the-art image classification methods require an intensive learning/training stage (using SVM, Boosting, etc.) In contrast, non-parametric Nearest-Neighbor (NN) based image classifiers require no training time and have other favorable properties. However, the large performance gap between these two families of approaches rendered NNbased image classifiers useless. We claim that the effectiveness of non-parametric NNbased image classification has been considerably undervalued. We argue that two practices commonly used in image classification methods, have led to the inferior performance of NN-based image classifiers: (i) Quantization of local image descriptors (used to generate “bags-of-words”, codebooks). (ii) Computation of ‘Image-to-Image’ distance, instead of ‘Image-to-Class’ distance. We propose a trivial NN-based classifier – NBNN, (Naive-Bayes Nearest-Neighbor), which employs NNdistances in the space of the local image descriptors (and not in the space of images). NBNN computes direct ‘Image-to-Class’ distances without descriptor quantization. We further show that under the Naive-Bayes assumption, the theoretically optimal image classifier can be accurately approximatedby NBNN. Although NBNN is extremely simple, efficient, and requires no learning/training phase, its performance ranks among the top leading learning-based image classifiers. Empirical comparisons are shown on several challenging databases (Caltech-101,Caltech-256 and Graz-01).
This is interesting because, to a certain extent, the random projection used the face recognition studies is also studied with regards to the nearest class not the nearest neighboring face. Hence, one could imagine a close relationship between random projections and other features normally found in Machine Learning such as SIFT. While we are on the subject of Machine Learning, Andrew Ng's course on the subject at Stanford is now on Youtube.
We consider the problem of recovering a matrix from its action on a known vector in the setting where the matrix can be represented efficiently in a known matrix dictionary. Connections with sparse signal recovery allows for the use of efficient reconstruction techniques such as Basis Pursuit. Of particular interest is the dictionary of time-frequency shift matrices and its role for channel estimation and identification in communications engineering. We present recovery results for Basis Pursuit with the time-frequency shift dictionary and various dictionaries of random matrices.
Finally, here are the stats for the first saturday morning cartoon. I was surprised to see a peakin the traffic to the website a day after its publication. Anyway, it fits the rule of thumb that in the first two days you see half of the eventual traffic over the week of the publication.
I wanted to have this episode talk about the different compressed sensing hardware. Alas for the time being, the application that produces these cartoons is having some problems rendering the cartoon for this morning. Sorry, it may take a little while.
Moshe Mishali, Yonina Eldar and Joel Tropp
