How Close is Compressive Sensing to Random Features with Random Kitchen Sinks?

I don't know but here is how the authors of [1] describe the Random KitcHen Sinks (RKS) for FastFood which are the non adaptive version of approaches like XNV. RKS seems to be a play on words for Reproducing Kernel Hilbert Spaces that one can use to approximate the identity (i.e. the reproducing property). From [1]

Random Kitchen Sinks (Rahimi & Recht, 2007;2008)1, the algorithm that our algorithm is based on, approximates the function f by means of multiplying the input with a Gaussian random matrix, followed by the application of a nonlinearity. If the expansion dimension is n and the input dimension is d (i.e., the Gaussian matrix is n x d), it requires O(nd) time and memory to evaluate the decision function f. For large problems with sample size mxn, this is typically much faster than the aforementioned \kernel trick" because the computation is independent of the size of the training set. Experiments also show that this approximation method achieves accuracy comparable to RBF kernels while offering significant speedup.

Potentially Interesting Reading

[1] Fastfood | Approximating Kernel Expansions in Loglinear Time, Quoc Le, Tam, Alex Smola

[2] Fast Functions via Randomized Algorithms: Linear Regression with Random Projections

Video: Fast Food: Approximating Kernel Expansion in Loglinear Time

[3] Video: Random Kitchen Sinks, Fast Food and other randomized kernel evaluations

[4] Fast Functions via Randomized Algorithms: Fastfood versus Random Kitchen Sinks,

[5] Compressed Sensing: Random Features for Large-Scale Kernel Machines

[6] Uniform Approximation of Functions with Random Bases, Ali Rahimi and Benjamin Recht
[7]The Summer of the Deeper Kernels

[8] Nystrom Method vs Random Fourier Features:: A Theoretical and Empirical Comparison Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, Zhi-Hua Zhou

[9 Pruning random features with correlated kitchen sinks -poster- Brian McWilliams and David Balduzzi
[11] XNV: Correlated random features for fast semi-supervised learning - implementation -[10] Learning Fastfood Feature Transforms for Scalable Neural Networks, Micol Marchetti-Bowick, Willie Neiswanger

Deep neural networks are flexible models that are able to learn complex nonlinear functions of data. The goal of this project is to build a shallow neural network that has the same representational power as a deep network by learning an extra nonlinear feature transformation at each node. To apply these transformations, we borrow techniques from the area of scalable, approximate kernel methods. In particular, we use the Fastfood method introduced by Le at al. in [1], which allows an approximate feature map for a transition-invariate kernel to be computed in log-linear time. Our method learns an optimal Fastfood feature expansion at each node while simultaneously optimizing the weight parameters of the neural network. We demonstrate our method on multiple datasets and show that it has better classification performance than neural networks with similar architectures.

Image Credit: NASA/JPL/Space Science Institute

Full-Res: W00086165.jpg

W00086165.jpg was taken on January 12, 2014 and received on Earth January 12, 2014. The camera was pointing toward SATURN at approximately 1,457,373 miles (2,345,415 kilometers) away, and the image was taken using the MT3 and CL2 filters.

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.