Saturday Morning Videos: Sub-Nyquist Sampling (Xampling) - Smart Sampling, Technion 2012

On Monday there will be a Workshop at the Technion in Yonina's lab. Here are the slides and videos of the 2012 workshop on Xampling and related techniques. 

Sub-Nyquist Sampling (Xampling) - Smart Sampling

Launching new area of activity in the EE Department, Technion. The activity will be based on research performed by a team led by Prof. Yonina Eldar and will include theoretical development and implementation of sub-Nyquist prototypes with applications to a wide variety of areas including radar, communication systems, medical imaging and optics. More...


The Smart Sampling Lab @ HSDSL by Prof. Yonina Eldar, EE Department, Technion
Slides and Video
More...

Defying Nyquist in Analog-to-Digital Conversion by Prof. Yonina Eldar, EE Department, Technion
Slides and Video
More...

Sparsity-Based Sub-Wavelength Imaging by Prof. Moti Segev, Physics Dep. and Solid State Institute, Technion

More...

Sub-Nyquist Sampling of Wideband Signals by Deborah Cohen, EE Department, Technion
Slides and Video
More...

Compressed Beamforming in Ultrasound Imaging by Noam Wagner, EE Department, Technion
Video
More...


Nonlinear Sampling with Application to Imaging by Tomer Michaeli, EE Department, Technion
Video
More...

Live Demonstration: Real-Time Sub-Nyquist Wideband Sensing by Rolf Hilgendorf, EE Department, Technion
Video
More...

The EE Department and Industry - Collaboration Mechanisms by Prof. Yitzhak (Tsahi) Birk, EE Department, Technion More...

Test and Measurement for Sub-Nyquist Sampling by James Kimery, Director of Marketing RF / Communications / SDR National Instruments
Video
More...

Wideband Front End: An Automotive Mobile Wireless Device Perspective by Dr. Kobi Scheim, General Motors

Simulation Platform for Signal Processing and Analysis of UWB Radar and Multi Fading Channels by Haim Spiegel, Agilent Technologies
Video

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Saturday Morning Videos: High Angle Take Offs

From the Avionist blog:

          Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Random Features and random projections

  This is the day where we catch up with Random Features and random projections

 

On the Error of Random Fourier Features by Dougal J. Sutherland, Jeff Schneider

Kernel methods give powerful, flexible, and theoretically grounded approaches to solving many problems in machine learning. The standard approach, however, requires pairwise evaluations of a kernel function, which can lead to scalability issues for very large datasets. Rahimi and Recht (2007) suggested a popular approach to handling this problem, known as random Fourier features. The quality of this approximation, however, is not well understood. We improve the uniform error bound of that paper, as well as giving novel understandings of the embedding's variance, approximation error, and use in some machine learning methods. We also point out that surprisingly, of the two main variants of those features, the more widely used is strictly higher-variance for the Gaussian kernel and has worse bounds.

 

 

Optimal Rates for Random Fourier Features  by Bharath K. Sriperumbudur, Zoltan Szabo

Kernel methods represent one of the most powerful tools in machine learning to tackle problems expressed in terms of function values and derivatives due to their capability to represent and model complex relations. While these methods show good versatility, they are computationally intensive and have poor scalability to large data as they require operations on Gram matrices. In order to mitigate this serious computational limitation, recently randomized constructions have been proposed in the literature, which allow the application of fast linear algorithms. Random Fourier features (RFF) are among the most popular and widely applied constructions: they provide an easily computable, low-dimensional feature representation for shift-invariant kernels. Despite the popularity of RFFs, very little is understood theoretically about their approximation quality. In this paper, we provide the first detailed theoretical analysis about the approximation quality of RFFs by establishing optimal (in terms of the RFF dimension) performance guarantees in uniform and Lr (1≤r<∞) norms. We also propose a RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.

Learning with Group Invariant Features: A Kernel Perspective by Youssef Mroueh, Stephen Voinea, Tomaso Poggio

We analyze in this paper a random feature map based on a theory of invariance I-theory introduced recently. More specifically, a group invariant signal signature is obtained through cumulative distributions of group transformed random projections. Our analysis bridges invariant feature learning with kernel methods, as we show that this feature map defines an expected Haar integration kernel that is invariant to the specified group action. We show how this non-linear random feature map approximates this group invariant kernel uniformly on a set of $N$ points. Moreover, we show that it defines a function space that is dense in the equivalent Invariant Reproducing Kernel Hilbert Space. Finally, we quantify error rates of the convergence of the empirical risk minimization, as well as the reduction in the sample complexity of a learning algorithm using such an invariant representation for signal classification, in a classical supervised learning setting.

DUAL-LOCO: Distributing Statistical Estimation Using Random Projections by Christina Heinze, Brian McWilliams, Nicolai Meinshausen

We present DUAL-LOCO, a communication-efficient algorithm for distributed statistical estimation. DUAL-LOCO assumes that the data is distributed according to the features rather than the samples. It requires only a single round of communication where low-dimensional random projections are used to approximate the dependences between features available to different workers. We show that DUAL-LOCO has bounded approximation error which only depends weakly on the number of workers. We compare DUAL-LOCO against a state-of-the-art distributed optimization method on a variety of real world datasets and show that it obtains better speedups while retaining good accuracy.

Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees by François-Xavier Briol, Chris J. Oates, Mark Girolami, Michael A. Osborne

There is renewed interest in formulating integration as an inference problem, motivated by obtaining a full distribution over numerical error that can be propagated through subsequent computation. Current methods, such as Bayesian Quadrature, demonstrate impressive empirical performance but lack theoretical analysis. An important challenge is to reconcile these probabilistic integrators with rigorous convergence guarantees. In this paper, we present the first probabilistic integrator that admits such theoretical treatment, called Frank-Wolfe Bayesian Quadrature (FWBQ). Under FWBQ, convergence to the true value of the integral is shown to be exponential and posterior contraction rates are proven to be superexponential. In simulations, FWBQ is competitive with state-of-the-art methods and out-performs alternatives based on Frank-Wolfe optimisation. Our approach is applied to successfully quantify numerical error in the solution to a challenging model choice problem in cellular biology.

Bilinear Random Projections for Locality-Sensitive Binary Codes by Saehoon Kim, Seungjin Choi

Locality-sensitive hashing (LSH) is a popular data-independent indexing method for approximate similarity search, where random projections followed by quantization hash the points from the database so as to ensure that the probability of collision is much higher for objects that are close to each other than for those that are far apart. Most of high-dimensional visual descriptors for images exhibit a natural matrix structure. When visual descriptors are represented by high-dimensional feature vectors and long binary codes are assigned, a random projection matrix requires expensive complexities in both space and time. In this paper we analyze a bilinear random projection method where feature matrices are transformed to binary codes by two smaller random projection matrices. We base our theoretical analysis on extending Raginsky and Lazebnik's result where random Fourier features are composed with random binary quantizers to form locality sensitive binary codes. To this end, we answer the following two questions: (1) whether a bilinear random projection also yields similarity-preserving binary codes; (2) whether a bilinear random projection yields performance gain or loss, compared to a large linear projection. Regarding the first question, we present upper and lower bounds on the expected Hamming distance between binary codes produced by bilinear random projections. In regards to the second question, we analyze the upper and lower bounds on covariance between two bits of binary codes, showing that the correlation between two bits is small. Numerical experiments on MNIST and Flickr45K datasets confirm the validity of our method.

Gradient-free Hamiltonian Monte Carlo with Efficient Kernel Exponential Families by Heiko Strathmann, Dino Sejdinovic, Samuel Livingstone, Zoltan Szabo, Arthur Gretton

We propose Kamiltonian Monte Carlo (KMC), a gradient-free adaptive MCMC algorithm based on Hamiltonian Monte Carlo (HMC). On target densities where HMC is unavailable due to intractable gradients, KMC adaptively learns the target's gradient structure by fitting an exponential family model in a Reproducing Kernel Hilbert Space. Computational costs are reduced by two novel efficient approximations to this gradient. While being asymptotically exact, KMC mimics HMC in terms of sampling efficiency and offers substantial mixing improvements to state-of-the-art gradient free-samplers. We support our claims with experimental studies on both toy and real-world applications, including Approximate Bayesian Computation and exact-approximate MCMC.

      Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Two Conferences: MMMA-2015, Moscow, August 2015 and CfP RSL-CV 2015, Santiago, Chile, Dec. 2015

Two meetings of interest:

Ivan just sent me the following:

Dear Igor,


we are organizing the 4-th international conference in Moscow on Matrices in Mathematics and Applications (MMMA-2015) http://matrix.inm.ras.ru/mmma-2015/ . Low-rank approximation of matrices and tensors will be the core topic of many talks.

I think it might be interesting to the readers of your blog. It is also a good time to visit Russia, since it is not very expensive now.

With best wishes,
Ivan Oseledets 

Thanks Ivan !

Andrews also sent me the following:

Hi Igor,

I'd like to forward you this call for paper for workshop on robust subspace learning and computer vision.

Best regards,

Andrews

Call for Paper for Workshop on

Robust Subspace Learning and Computer Vision (RSL-CV 2015)

Santiago, Chile, in conjunction with ICCV 2015 (http://pamitc.org/iccv15/)

Recent research on robust subspace learning and tracking by decomposition into low-rank plus additive matrices provides a suitable framework for computer vision applications such as video coding, key frame extraction, hyper-spectral video processing, dynamic MRI, motion saliency detection and background/foreground separation. In this context, decomposition into low rank plus sparse matrices has been developed in different formulation problems such as robust principal component analysis, robust non-negative matrix factorization, robust matrix completion, subspace tracking, and low-rank minimization
The aim of RSL-CV 2015 (http://rsl-cv2015.univ-lr.fr/workshop/) are three-fold: 1) proposing robust subspace learning and tracking for computer vision applications, 2) proposing new adaptive and incremental algorithms for robust subspace learning and tracking to reach the requirements of real-time applications such as background/foreground separation, motion saliency and video coding, and 3) proposing robust algorithms to tackle key challenges in applications such as dynamic backgrounds and illumination changes for background/foreground separation.
IMPORTANT DATES
Intention to Submit (not mandatory):           June 30, 2015 (with a tentative title to send to tbouwman@univ-lr.fr)
Full Paper Submission Deadline:                   September 1, 2015 (for papers not submitted at ICCV)
                                                                      September 10, 2015 (for papers that are awaiting for ICCV decisions)
Decisions to Authors:                                    October 1, 2015
Camera-ready Deadline:                               October 16, 2015

MAIN ORGANIZERS
Thierry Bouwmans, Laboratoire MIA, Univ. La Rochelle, France.
Paul Rodriguez, DSP / DIP Laboratory, Pontificia Universidad Católica del Perú. Peru.
Namrata Vaswani, Iowa State University. USA.
Brendt Wohlberg, Los Alamos National Laboratory, USA.
John Wright, Department of Electrical Engineering, Columbia University, USA.
El-Hadi Zahzah, Laboratoire L3I, Univ. La Rochelle, France.

PROGRAM COMMITTEE (To be completed)
Necdet Serhat Aybat, Pennsylvania State University, USA
Jun He, Nanjing University of Information Science and Technology, China
Soon Ki Jung, Kyungpook National University, Korea
Shiqian Ma, Chinese University of Hong Kong, China

Gonzalo Mateos, Univ. of Rochester, USA 

Lucia Maddalena, National Research Council, Italy
Shinichi Nakajima, Technische Universität Berlin, Germany
Fatih Porikli, NICTA and Australian National University, Australia
Caifeng Shan, Philips Research, The Netherlands (To be confirmed)
Xianbiao Shu, Qualcomm, San Diego, USA

PUBLICATIONS
Accepted papers will be published in the ICCV 2015 Workshop Proceedings. Selected papers, after extensions and further revisions, will be published in a special issue in an international journal.

Thanks Andrews !

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Paris Machine Learning Meetup #10 Season 2 Finale: "And so it begins": Deep Learning, Recovering Robots, Vowpal and Hadoop, Predicsis, Matlab, Bayesian test, Experiments on #ComputationalComedy & A.I.

Here is the streaming feed for tonight. The program is below: 

Video Feed

For this last regular meetup of the season (the season 2 finale), we will be were invited by the good folks at Mathworks and will have had the meetup at UPMC. The meetup started at 6:50PM Paris time.

Here is the program with the attendant slides. Most talks were in French (slides are in English always) except where noted. For those who speak english only, three presentations were spoken in English. We put them next to each other to have an "English session". That English speaking session  started at about 58 minutes and 22 seconds in the video with Samim and finished roughly at 2 hours 05 minutes with Florence.


+ Franck Bardol, Igor Carron, Meetup Presentation 
(talk given in French)

+ Olivier Corradi,  Snips.net Lightning talk (at 7minutes and 19 seconds in the video) Presentation slides
(talk given in French)

Snips is using artificial intelligence to make technology disappear. We're launching a unique lab to experiment with new technology - and we need your help to build it.

+ Heloise Nonne, Quantmetry, "Online learning, Vowpal Wabbit and Hadoop"
(talk given in French at 12 minutes and 19 seconds in the video)

Online learning has recently caught a lot of attention, following some competitions, and especially after Criteo released a very large dataset for a Kaggle contest.

Online learning allows to process massive data as the learner processes data in a sequential way using up a low amount of memory and limited CPU ressources. It is also particularly suited for handling time-evolving data or for exploring data set and testing many combination of features.

Vowpal Wabbit has become quite popular: it is a handy, light and efficient command line tool allowing to do online learning on GB of data, even on a standard laptop with standard memory. After a reminder of the online learning principles, I'll present the advantages of Vowpal Wabbit and the way it can be parallelized on Hadoop in a distributed fashion.

+ Amine El Helou, Laurence Vachon, MathWorks. “MATLAB for Data Science and Machine Learning”
(talk given in French at 35 minutes and 50 seconds in the video)

An integrated data analytics workflow: developing data-driven predictive models with MATLAB.

+ Samim Winiger, "Experiments on #ComputationalComedy and A.I."  (remote from Berlin and in English , starts at 58 minutes and 22 seconds in the video)

Example of work: Obama-RNN — Machine generated political speeches but also TED-RNN — Machine generated TED-Talks, Ideas worth generating and attendant Video.

+ Ruslan Salakhutdinov, University of Toronto, Learning Multimodal Deep Models  (remote from Toronto and in English, starts at 1 hour 06 minutes and 08 seconds in the video)

+ Florence Benezit-Gajic, PredicSis, "PredicSis: Prediction API"
(talk given in English, starts at 1 hour 47 minutes and 55 seconds in the video)

Not every predictive API are born equal. Come and take a look at PredicSis API.

+ Jean-Baptiste Mouret, INRIA/UPMC, "Robots that can recover from damage in minutes" . Attendant video:  https://youtu.be/T-c17RKh3uE -
(talk given in French, starts at 2 hours 06 minutes and 40 seconds in the video)

A major obstacle to the widespread adoption of robots in uncontrolled environments (i.e. outside of factories) is their fragility. In this talk, we describe a trial-and-error learning algorithm that allows robots to adapt to damage in less than two minutes, and thus will enable more robust, effective, autonomous robots.

http://chronos.isir.upmc.fr/~mouret/website/nature_press.xhtml#faq

+ Christian Robert Paris Dauphine, "Testing as estimation: the demise of the Bayes factors"
(talk given in French, starts at 2 hours 26 minutes and 00 seconds in the video)

We consider a novel paradigm for Bayesian testing of hypotheses and Bayesian model comparison. Our alternative to the traditional construction of posterior probabilities that a given hypothesis is true or that the data originates from a specific model is to consider the models under comparison as components of a mixture model. We therefore replace the original testing problem with an estimation one that focus on the probability weight of a given model within a mixture model. We analyze the sensitivity on the resulting posterior distribution on the weights of various prior modeling on the weights. We stress that a major appeal in using this novel perspective is that generic improper priors are acceptable, while not putting convergence in jeopardy. Among other features, this allows for a resolution of the Lindley-Jeffreys paradox. http://arxiv.org/abs/1412.2044

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Fast and Guaranteed Tensor Decomposition via Sketching

 

More goodies in the tensor realm, and according to Anima, an implementation will be shortly available. Here is the paper: Fast and Guaranteed Tensor Decomposition via Sketching by Yining Wang, Hsiao-Yu Tung, Alexander Smola, Animashree Anandkumar

Tensor CANDECOMP/PARAFAC (CP) decomposition has wide applications in statistical learning of latent variable models and in data mining. In this paper, we propose fast and randomized tensor CP decomposition algorithms based on sketching. We build on the idea of count sketches, but introduce many novel ideas which are unique to tensors. We develop novel methods for randomized computation of tensor contractions via FFTs, without explicitly forming the tensors. Such tensor contractions are encountered in decomposition methods such as tensor power iterations and alternating least squares. We also design novel colliding hashes for symmetric tensors to further save time in computing the sketches. We then combine these sketching ideas with existing whitening and tensor power iterative techniques to obtain the fastest algorithm on both sparse and dense tensors. The quality of approximation under our method does not depend on properties such as sparsity, uniformity of elements, etc. We apply the method for topic modeling and obtain competitive results.

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Riemannian preconditioning for tensor and matrix completion - implementation(s) -

 

Bamdev just sent me the following: 

 

 Dear Igor,

I wish to share our recent technical report on "Riemannian preconditioning for tensor completion", available at http://arxiv.org/abs/1506.02159. The results are promising.


It works with the fixed-rank Tucker manifold by endowing it with a "preconditioned" Riemannian geometry. The preconditioned geometry results from exploiting the two fundamental structures of the completion problem, i.e.,
1) the quadratic structure of the cost function and
2) the non-uniqueness of Tucker decomposition.


The code is available at http://bamdevmishra.com/codes/tensorcompletion/. It is built on the Manopt toolbox for optimization on manifolds.

The work actually builds upon the earlier work on matrix completion "R3MC: A Riemannian three-factor algorithm for low-rank matrix completion", available at http://arxiv.org/abs/1306.2672. The code is at http://bamdevmishra.com/codes/r3mc/.


The general preconditioning idea is motivated in "Riemannian preconditioning", available at http://arxiv.org/abs/1405.6055. 

Regards,
Bamdev

Thanks Bamdev ! Here are the attendant papers:

 

Riemannian preconditioning for tensor completion by Hiroyuki Kasai, Bamdev Mishra

We propose a novel Riemannian preconditioning approach for the tensor completion problem with rank constraint. A Riemannian metric or inner product is proposed that exploits the least-squares structure of the cost function and takes into account the structured symmetry in Tucker decomposition. The specific metric allows to use the versatile framework of Riemannian optimization on quotient manifolds to develop a preconditioned nonlinear conjugate gradient algorithm for the problem. To this end, concrete matrix representations of various optimization-related ingredients are listed. Numerical comparisons suggest that our proposed algorithm robustly outperforms state-of-the-art algorithms across different problem instances encompassing various synthetic and real-world datasets.

R3MC: A Riemannian three-factor algorithm for low-rank matrix completion by B. Mishra, R. Sepulchre

We exploit the versatile framework of Riemannian optimization on quotient manifolds to develop R3MC, a nonlinear conjugate-gradient method for low-rank matrix completion. The underlying search space of fixed-rank matrices is endowed with a novel Riemannian metric that is tailored to the least-squares cost. Numerical comparisons suggest that R3MC robustly outperforms state-of-the-art algorithms across different problem instances, especially those that combine scarcely sampled and ill-conditioned data.

 

Riemannian preconditioning by Bamdev Mishra, Rodolphe Sepulchre

The paper exploits a basic connection between sequential quadratic programming and Riemannian gradient optimization to address the general question of selecting a metric in Riemannian optimization, in particular when the Riemannian structure is sought on a quotient manifold. The proposed method is shown to be particularly insightful and efficient in quadratic optimization with orthogonality and/or rank constraints, which covers most current applications of Riemannian optimization in matrix manifolds.

 

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Modulated Unit-Norm Tight Frames for Compressed Sensing - implementation -

Lu Gan just sent me the following:

Dear Igor,

.... You have mentioned our work about "scrambled hadamard transform" and "spinning disk for terahertz imaging" on your blog before. I really appreciate that.
With this Email, I would to let you know 2 of our recent research work

1) We proposed a new unified framework for the construction of structured random matrices for compressed sensing. Under this framework, the RIP results of some popular structured sensing matrices (e.g. compressive multiplexing, random demodulation) can be easily analyzed and improved. We also propose several new structured sensing matrices based on the framework. The paper will be published on IEEE Trans. on Signal Processing soon.

You can find the paper from either of the following links:
http://arxiv.org/abs/1411.7630

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7093188&queryText=modulated+unit+norm+tight+frames&newsearch=true&searchField=Search_All

The code related to the paper is available at:
https://github.com/p-zhang/p-zhang.github.io/tree/master/archive/myresearch/udb_matlab_code

2) We have also done some work on dictionary learning for 3D terahertz imaging, which was published on Elsevier Digital Signal processing. The abstract can be found on the following link:

http://www.sciencedirect.com/science/article/pii/S1051200415001426
Subsampled terahertz data reconstruction based on spatio-temporal dictionary learning

Thanks in advance and have a nice weekend!

Best,
Lu

 Thank you Lu !

Modulated Unit-Norm Tight Frames for Compressed Sensing by Peng Zhang, Lu Gan, Sumei Sun, Cong Ling

In this paper, we propose a compressed sensing (CS) framework that consists of three parts: a unit-norm tight frame (UTF), a random diagonal matrix and a column-wise orthonormal matrix. We prove that this structure satisfies the restricted isometry property (RIP) with high probability if the number of measurements m=O(slog2slog2n) for s-sparse signals of length n and if the column-wise orthonormal matrix is bounded. Some existing structured sensing models can be studied under this framework, which then gives tighter bounds on the required number of measurements to satisfy the RIP. More importantly, we propose several structured sensing models by appealing to this unified framework, such as a general sensing model with arbitrary/determinisic subsamplers, a fast and efficient block compressed sensing scheme, and structured sensing matrices with deterministic phase modulations, all of which can lead to improvements on practical applications. In particular, one of the constructions is applied to simplify the transceiver design of CS-based channel estimation for orthogonal frequency division multiplexing (OFDM) systems.

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Saturday Morning Videos: High Altitude Balloon with Android

      Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Isometric sketching of any set via the Restricted Isometry Property

 

 

In compressive sensing, the earliest results used randomization as a way to compress signals. But it is in fact deeper. This week, we saw in Extreme Compressive Sampling for Covariance Estimation that sparsity was not central to the argument of dimension reduction. Here is another paper that further enlighten us on this very specific issue. From the paper:

At the heart of our analysis is a theorem that shows that matrices that preserve the Euclidean norm of sparse vectors (a.k.a. RIP matrices), when multiplied by a random sign pattern preserve the Euclidean norm of any set. Roughly stated, linear transforms that provide low distortion embedding of sparse vectors also allow low distortion embedding of any set! We believe that our result provides a rigorous justification for replacing “slow” Gaussian matrices with “fast” and computationally friendly matrices in many scientific and engineering disciplines. Indeed, in a companion paper [18] we utilize our results in this paper to develop sharp rates of convergence for various optimization problems involving such matrices.

my emphasis.

 

Isometric sketching of any set via the Restricted Isometry Property by Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi

In this paper we show that for the purposes of dimensionality reduction certain class of structured random matrices behave similarly to random Gaussian matrices. This class includes several matrices for which matrix-vector multiply can be computed in log-linear time, providing efficient dimensionality reduction of general sets. In particular, we show that using such matrices any set from high dimensions can be embedded into lower dimensions with near optimal distortion. We obtain our results by connecting dimensionality reduction of any set to dimensionality reduction of sparse vectors via a chaining argument.

 

Credit: Date: 28 May 2015
Satellite: Rosetta Depicts: Comet 67P/Churyumov-Gerasimenko Copyright: ESA/Rosetta/NAVCAM, CC BY-SA IGO 3.0

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.