Gradient Descent with Sparsification: An Iterative Algorithm for Sparse Recovery with Restricted Isometry Property

by Rahul Garg and Rohit Khandekar

This paper tells one story about the following optimization problem arising from compressive sampling

\min_x \quad \| x \|_0 \qquad \text{s.t.} \quad \Phi x = y,

which is usually approximated with the following version

\min_x \quad \| x \|_1 \qquad \text{s.t.} \quad \Phi x = y.

We have quite a few algorithms for solving the optimization under different conditions. This paper proposes the following gradient-based algorithm

x \leftarrow H_s \left( x + \frac{1}{\gamma} \cdot \Phi^\top (y - \Phi x)\right)

where H_s take the largest (absolute value) s elements of x and other as 0.

The theoretical result is their small computation cost (K in each iteration), fast convergence rate (2L / \log(\frac{1 - \delta_{2s}}{2\delta_{2s}})) and lenient recovery condition (\delta_{2s} < \frac{1}{3}). I think it might be a good algorithm if we late want to make some lasso experiments.

High-dimensional Data Analysis: The Curses and Blessings of Dimensionality

by David L. Donoho

In this non-technical paper, Donoho prospected the development of data analysis and suggested the difficulty in dealing with high dimensional data (the curse of dimensionality) and the possible advantages we may take (the blessing of dimensionality). His advisor John Tuckey coined the word data analysis, which differs from the traditional mathematics or statistics in the way of rigorous derivation: more heuristic ideas are applied. He argued that nowadays people choose quite a different method of exploration in science: only a few variables are selected to make a model which can be analytically formulated and studied in the traditional way while now it is more widely employed to collect a large amount of data or the information about one sample is enriched via all kinds of ways.

Curse of Dimensionality:

• For a naive search algorithm in a high dimensional discrete space, the number of candidates is exponential of the dimensionality.
• For optimization, we need (1/\epsilon)^d evaluations for a Lipschitz continuous objective function for an approximation of error less than \epsilon.
• In function approximation to a Lipschitz continous function, we also need O\big((1/\epsilon)^d \big) evaluations for a uniform approximation of error \epsilon.
• In numeric integration of a Lipschitz continous function, again we need O\big( (1/\epsilon)^d\big) evaluations on a grid in order to obtain an approximate integration of error \epsilon.
• Nonparametric extimation will be difficult. The much slower convegence rate is the ugly head of the curse of dimensionality.
• Regularization is usually employed to tackle the curse of dimensionality.
  

Blessing of Dimensionality:

• The concentration of measure phenomenon is for a lot of distribution in the high dimensional space. Let (\Omega, \mathcal{F}, \mu) be a metric measurable space, d(\cdot, \cdot) is the distance and \mu is the probability measure of the \sigma-field \mathcal{F}. Let \alpha(\epsilon) = \sup_A \{ \mu( \Omega \backslash A_\epsilon) \mid \mu(A) = 1/2\} where A_\epsilon = \{ x \in \Omega \mid d(x, A) < \epsilon\} is the \epsilon-extension of the measurable set A. The so-called Levy family (\Omega_n, \mathcal{F}_n, \mu_n), which satisfies \forall \epsilon > 0, \lim_{n \to \infty} \alpha_n(\epsilon) = 0, means that the probability measure will concentrate in the center part of the support when n increase. If the convergence to 0 is C \exp(-c n \epsilon^2), then it is also called normal Levy family. In many cases, the index n can be the dimensionality, which means as the dimensionality goes up, we may observe the concentration of measure. For a normal Levy family, the tail's behavior is like a Gaussian. The concentration of measure means in high dimensional space it is more likely that the data you sample contains much information as you don't need to go further from the data, you have already covered the support. The probability decays as you leave a set with a fixed nonzero measure set.
• Dimension asymptotics. This is the refinement of the previous argument.
• Approach to continuum: there is an underlying compactness to the space of observed data which will be reflected by approximate finite-dimensionality and an increasing simplicity of analysis for large d. (sounds like the reason for compressive sensing).
• Approximation through randomness. Random projections, CS are in this range.
• Approximation through computational harmonic analysis, which is a way to the continuum.
  

I am not familiar with harmonic analysis. Many points in this paper are still vague to me. I must reread it when I gain more knowledge.

Random Projection for Manifold Learning

by Chinmay Hedge and Michael B. Wakin and Richard G. Baraniuk

This paper tells us that we may project the data from a higher dimensional space (n dimensions) into a random subspace (m dimensions) and we will not lose much information of the intrinsic structural information. Therefore we may apply one of the manifold learning algorithms to the randomly-projected data and still recover their structure in a proper space (d dimensions). And d < m << n and m = O(d log n).

The first theorem comes from RIP satisfaction, when

m \geq O\left( \frac{d \log (n V \tau^{-1}) \log(\rho^{-1})}{\epsilon^2}\right)

with probability no less than 1-ρ, for any x, z, we have

(1 - \epsilon) \sqrt{\frac{m}{n}} \leq \frac{d_i( \Phi x, \Phi z)}{d_i( x, z )} \leq (1 - \epsilon) \sqrt{\frac{m}{n}},

where Φ is the random orthogonal projection, V is the volume and 1/τ is the condition number of the latent manifold. To estimate the intrinsic dimensions, the author propose to employ Grassberger-Procaccia algorithm (based on correlation). They found bounds for the estimated dimensions: when

m \geq O\left( \frac{d \log( n V \tau^{-1}) \log (\rho^{-1})}{\beta^2 \delta^2} \right),

then the estmated correlation dimension satisfies

(1 - \delta) \hat{d} \leq \hat{d}_\Phi \leq (1 + \delta) \hat{d},

with probability exceeding 1-ρ. And the residual variance of the ISOMAP embedding is also bounded

R_\Phi \leq R + C \Gamma^2 \epsilon,

where Γ is the diameter of the point cloud.

Since in practice we are not sure about the intrinsic dimensionality, we usually try to add more orthogonal vectors and see whether the residual variance is small enough.

Well it is atypical way of applying CS in machine learning. Put all data in a random projection subspace and prove there are bounds for later learning algorithms. It is not the way I'd like to use CS.

Compressive Sampling

by Emamnuel J. Candès

This is the first paper I read about compressive sampling (a.k.a. compressed sensing). The main idea of CS is that we have a measure matrix Φ and a different representation matrix Ψ and they are quite different. The traditional way of signal processing would use the same matrix for measurement and representation. The Nyquist-Shannon theorem says we need a bandwidth as large as the connected support in Φ-domain. But in practice our signal is usually sparse in Ψ-domain but the sparse weights are not in a connected subset of the whole space. Therefore to apply N-S thereom, we need a large bandwidth to transmit the data. But then we might think we might miss the sparsity point.

The new findings in CS say that if the measurement Φ satisfies a certain condition, we might recover the sparse encoding in Ψ-domain with a linear programming solver:

min | x |₁ subject to ΦΨx=y

where y is the measurement of the groundtruth (i.e. Φf, where f is the original signal).

The measurement matrix Φ must satisfy the UUP (uniform uncertainty principle) or RIP (restricted isometry principle). To put it simple, it means that any subset of coordinates (cardinality less than S) under the transform of the corresponding part of Φ will keep the norm in a certain bound. This bound implies when the exact decoding will be successful. Many stochastic matrix can be candidates for Φ, e.g. Gaussian, binary, Fourier (randomly selected rows of Fourier transform), incoherent measurement (randomly selected rows of random orthoganal matrix). Experts are busy proving how few rows we need for exact decoding. That is to prove a tight upper bound for S(sparsity of Ψ-domain) with N(length of the signal) and K(number of measurements, #rows of Φ).

It can be proved that the recovered x is optimal in a sense. This idea can still be extend to the case of signal with noise.

There are research of CS in machine learning, exploiting the sparsity part. Since as SVM or RVM suggests, the classifier in the dual representation should be sparse. Therefore it seems possible to train a model in a randomly projected space without losing information. There has been work in this part. I will explore more about it later. For now we just need their idea.