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.

Randomer Forests - implementation -

Using random projection in a random forest approach. Interesting !

From the paper, I note the connection to Robst PCA

Moreover, we demonstrate that a variant of RerF is approximately is both affine invariant and robust to outliers, two properties that are relatively easy to obtain independently, though difficult to obtain jointly and inexpensively (see recent work on robust PCA following Candes et al., 2009 [9]).

and further:

Instead we use random projections: we generate matrices A that are distributed in a rotation invariant fashion, but maintain the space and time complexity of RFs, by employing very sparse random projections [10]. Rather than sampling d non-zero elements of A, enforcing that each column gets a single non-zero number (without replacement), which is always1, we relax these constraints and select d non-zero numbers from f

Here is the paper: Randomer Forests by Tyler M. Tomita, Mauro Maggioni, Joshua T. Vogelstein

Random forests (RF) is a popular general purpose classifier that has been shown to outperform many other classifiers on a variety of datasets. The widespread use of random forests can be attributed to several factors, some of which include its excellent empirical performance, scale and unit invariance, robustness to outliers, time and space complexity, and interpretability. While RF has many desirable qualities, one drawback is its sensitivity to rotations and other operations that "mix" variables. In this work, we establish a generalized forest building scheme, linear threshold forests. Random forests and many other currently existing decision forest algorithms can be viewed as special cases of this scheme. With this scheme in mind, we propose a few special cases which we call randomer forests (RerFs). RerFs are linear threshold forest that exhibit all of the nice properties of RF, in addition to approximate affine invariance. In simulated datasets designed for RF to do well, we demonstrate that RerF outperforms RF. We also demonstrate that one particular variant of RerF is approximately affine invariant. Lastly, in an evaluation on 121 benchmark datasets, we observe that RerF outperforms RF. We therefore putatively propose that RerF be considered a replacement for RF as the general purpose classifier of choice. Open source code is available at this http URL

      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 Maxout Features look like Quantized JL Embeddings

This Great Convergence in Action has another example today. Folks from different fields doing very similar things with sometimes different vocabulary.

Random Maxout Features by Youssef Mroueh, Steven Rennie, Vaibhava Goel

In this paper, we propose and study random maxout features, which are constructed by first projecting the input data onto sets of randomly generated vectors with Gaussian elements, and then outputing the maximum projection value for each set. We show that the resulting random feature map, when used in conjunction with linear models, allows for the locally linear estimation of the function of interest in classification tasks, and for the locally linear embedding of points when used for dimensionality reduction or data visualization. We derive generalization bounds for learning that assess the error in approximating locally linear functions by linear functions in the maxout feature space, and empirically evaluate the efficacy of the approach on the MNIST and TIMIT classification tasks.

Obviously, this is very similar to the Quantized Johnson-Lindenstrauss embeddings explored in part by Petros Boufounos and others. In the recent video by Petros, it starts at 15 minutes and 30 seconds.....

.... and the figure that resembles figure 1 of the previous paper is at 19 minutes and 57 seconds.

      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.

Sparse Proteomics Analysis - A compressed sensing-based approach for feature selection and classification of high-dimensional proteomics mass spectrometry data - implementation -

The knowledge generated by the genome only makes sense if one can do a good job at figuring out what sort of proteins are producing by different elements of the DNA. Hence, while GWAS studies are great and the alignement issues in sequencing is becoming easier to handle, the big unknown is now to connect information with the zoo of proteins produced by the body. That effort includes sensing the right thing in a very large dimensional space, the subject of today's paper. Let us hope it guides us into producing better sensors . And yes as the article says

"a [Machine Learning] classification problem is equivalent to 1-bit CS " 

Without further ado Sparse Proteomics Analysis - A compressed sensing-based approach for feature selection and classification of high-dimensional proteomics mass spectrometry data by Tim Conrad, Martin Genzel, Nada Cvetkovic, Niklas Wulkow, Alexander Leichtle, Jan Vybiral, Gitta Kutyniok, Christof Schütte

Motivation: High-throughput proteomics techniques, such as mass spectrometry (MS)-based approaches, produce very high-dimensional data-sets. In a clinical setting one is often interested how MS spectra differ between patients of different classes, for example spectra from healthy patients vs. spectra from patients having a particular disease. Machine learning algorithms are needed to (a) identify these discriminating features and (b) classify unknown spectra based on this feature set. Since the acquired data is usually noisy, the algorithms should be robust to noise and outliers, and the identified feature set should be as small as possible.
Results: We present a new algorithm, Sparse Proteomics Analysis (SPA), based on the theory of Compressed Sensing that allows to identify a minimal discriminating set of features from mass spectrometry data-sets. We show how our method performs on artificial and real-world data-sets.

The attendant code is here: http://medicalbioinformatics.de/index.php?option=com_content&view=article&id=19

  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.

Extreme Compressive Sampling for Covariance Estimation

 

 

What can you learn from the sample covariance of a signal from its compressive measurements, today we have an answer on this issue from Extreme Compressive Sampling for Covariance Estimation by Martin Azizyan, Akshay Krishnamurthy, Aarti Singh

We consider the problem of estimating the covariance of a collection of vectors given extremely compressed measurements of each vector. We propose and study an estimator based on back-projections of these compressive samples. We show, via a distribution-free analysis, that by observing just a single compressive measurement of each vector one can consistently estimate the covariance matrix, in both infinity and spectral norm. Via information theoretic techniques, we also establish lower bounds showing that our estimator is minimax-optimal for both infinity and spectral norm estimation problems. Our results show that the effective sample complexity for this problem is scaled by a factor of m2/d2 where m is the compression dimension and d is the ambient dimension. We mention applications to subspace learning (Principal Components Analysis) and distributed sensor networks.

Credit: NASA, APL, SwRI

Description: OpNav Campaign 4, LORRI 4X4
Time: 2015-06-11 05:29:16 UTC
Exposure: 2967 msec
Target: PLUTO
Range: 39.6M km
  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.

Democratic Representations - implementation -

Christoph just sent me the following:

Hi Igor,


We finally managed to prepare a simple software package that includes three efficient solvers that compute democratic representations via infinity-norm minimization. The MATLAB software package can be found here:

http://www.csl.cornell.edu/~studer/software_demo.html

The papers describing our algorithms can be found—as always—on arXiv:

http://arxiv.org/abs/1401.3420
http://arxiv.org/abs/1202.4034

Best,
Christoph

-----------------------------------------
Christoph Studer
Assistant Professor
School of ECE, Rhodes Hall 331
Cornell University
Ithaca, NY 14853, USA
Web: www.csl.cornell.edu/~studer

Thanks Christoph ! I think this is the first time we have a phase transition diagram for these anti-sparse decompositions.

 

Democratic Representations  by Christoph Studer, Tom Goldstein, Wotao Yin, Richard G. Baraniuk

Minimization of the ℓ∞ (or maximum) norm subject to a constraint that imposes consistency to an underdetermined system of linear equations finds use in a large number of practical applications, including vector quantization, approximate nearest neighbor search, peak-to-average power ratio (or "crest factor") reduction in communication systems, and peak force minimization in robotics and control. This paper analyzes the fundamental properties of signal representations obtained by solving such a convex optimization problem. We develop bounds on the maximum magnitude of such representations using the uncertainty principle (UP) introduced by Lyubarskii and Vershynin, and study the efficacy of ℓ∞-norm-based dynamic range reduction. Our analysis shows that matrices satisfying the UP, such as randomly subsampled Fourier or i.i.d. Gaussian matrices, enable the computation of what we call democratic representations, whose entries all have small and similar magnitude, as well as low dynamic range. To compute democratic representations at low computational complexity, we present two new, efficient convex optimization algorithms. We finally demonstrate the efficacy of democratic representations for dynamic range reduction in a DVB-T2-based broadcast system.

PAR-Aware Large-Scale Multi-User MIMO-OFDM Downlink  by Christoph Studer, Erik G. Larsson

We investigate an orthogonal frequency-division multiplexing (OFDM)-based downlink transmission scheme for large-scale multi-user (MU) multiple-input multiple-output (MIMO) wireless systems. The use of OFDM causes a high peak-to-average (power) ratio (PAR), which necessitates expensive and power-inefficient radio-frequency (RF) components at the base station. In this paper, we present a novel downlink transmission scheme, which exploits the massive degrees-of-freedom available in large-scale MU-MIMO-OFDM systems to achieve low PAR. Specifically, we propose to jointly perform MU precoding, OFDM modulation, and PAR reduction by solving a convex optimization problem. We develop a corresponding fast iterative truncation algorithm (FITRA) and show numerical results to demonstrate tremendous PAR-reduction capabilities. The significantly reduced linearity requirements eventually enable the use of low-cost RF components for the large-scale MU-MIMO-OFDM downlink.

    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.