"Given a subset K of the unit Euclidean sphere, we estimate the minimal number m = m(K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x,y in K is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m = O(w(K)^2) where w(K) is the Gaussian mean width of K."

L1 dimension reduction??

"This paper describes a new thresholding technique for constructing sparse principal components."

"Among our key results: (i) Determining a likely range for the big-Oh constant in practice for the dimension of the target space, and demonstrating the accuracy of the predicted bounds. (ii) Finding ‘best in class’ algorithms over wide ranges of data size and source dimensionality, and showing that these depend heavily on parameters of the data as well its sparsity. (iii) Developing the best implementation for each method, making use of non-standard optimized codes for key subroutines. (iv) Identifying critical computational bottlenecks that can spur further theoretical study of efficient algorithms."

"We give a tutorial overview of several foundational methods for dimension reduction. We divide the methods into projective methods and methods that model the manifold on which the data lies...Although the review focuses on foundations, we also provide pointers to some more modern techniques. We also describe the correlation dimension as one method for estimating the intrinsic dimension, and we point out that the notion of dimension can be a scale-dependent quantity."

Six months of high-dimensional inference lectures.

Screw the kernel trick; just run your learning algorithm in the measurement domain. Similar to how Blum et al screwed the kernel trick with the Johnson-Linderstrauss lemma.

Screw the kernel trick; just take your high dimensional data and hash it.