Data Science Part 19: Sparsity/Bases

Let's move on to the new topic of sparsity and bases. The first thing we want to discuss is in sparse signal processing. What exactly is sparsity? It can either be represented by an orthonormal basis, or a tight frame. This is where a signal is represented more efficiently in terms of the sparse vector of coefficients in a generic transform basis, such as Fourier or wavelet bases. We can now acquire compressed measurements and solve for the sparest high-dimensional signal that is consistent with the measurements, which is called compressed sensing. It helps with stinginess, frugality, and just saving money in general in terms of resources used. It can be represented by the equation 

.

The coefficient αi is the projection of the signal x onto the basis function ψi. For the maximum efficiency, we want to choose the basis ψ so that the coefficients αi are sparse, meaning that most are 0 or close to 0. We can represent this through smooth signals, and Fourier sinusoids. In approximation, we want to quantize/encode coefficient sizes and locations. In a linear approximation we will keep the same coefficients for each signal. However, in a nonlinear approximation, we will want to use the K biggest coefficients. In the below picture, we choose whichever signals are the largest: 

Many signals are sparse in some sort of representation basis. 

When a signal is K-sparse, this means that there are exactly  K nonzero elements. I will next describe the typical sensing/compressing setup. we can get small coefficients by taking the fourier signal, and then we just need to take the inverse transform to reconstruct the original signal. 

In compression, we transform, sort the coefficients, and encode the K largest ones. Encoding is the position of the nonzero coefficients in their values. there is lots of work to throw away, around 80% of the coefficients, and the work process goes something like this: 

Let's talk about what a base is and how to select one. The main idea is that we want a good approximation of a signal using a few large coefficients. We will first consider taking the transform coefficients and sorting them. The orthonormal bases preserve energy and we want the K largest coefficients that contain the most signal energy. A good transform compacts the energy well, while the energy is spread around evenly in a bad transform.  If [v1, . . . , VN ] is an orthonormal basis that spans a vector space V, then Vector X ∈ V can be expressed as 

where αi = <xi, vi>. We can also use a correction term for proper normalization. Basis vectors are linearly independent so they need to be orthonormal. 

Smooth 1D functions or functions with significant discontinuities are effectively well-represented by Fourier transform. To compress the image, we first arrange all of the Fourier coefficients in order. To compress the image, we first arrange all of the Fourier coefficients in order and finally take inverse FFT. 

Two dimensional signal representations help greatly in introducing more structure. We can use Fourier signal in 2D component. However, we have discontinuities  along 1D contour and the 2D wavelets fail to capture the structure. The response to this is to implement various types of tight frames. 

Let's recall our old friend Fourier. We have Fast Θ(N x log(N)) processing for the discrete Fourier transform, and it's great for sparse representation of smooth functions. There are also versions for multi-dimensional signals. 

In an orthonormal transform, we consider vector space V of dimension N with inner product. We are spanned by vectors [V1, ..., VN]. The inner products satisfy <Vi, Vj> = 1 when i = j and 0 elsewise. Orthonormal (orthogonal) matrices are matrices in which the columns vectors form an orthonormal set (each column vector has length one and is orthogonal to all the other column vectors (dot product of 0)).

We can now write any vector x in space V with coordinates. We have a one-to-one mapping between v and α. αi = <x, vi>. There is a one to one mapping between v and α. Here's the formula for computing the coefficient: 

An example is the discrete time Fourier basis. Here is the description of the DTFB: 

The useful result 1 is that all linear transforms T over V can now be represented by the matrix

Input x -> T -> Output y. 

The useful result 2 is that the spectral theorem, where the matrix representation yields eigenvectors, passed through the system with multiplication. 

Let's now discuss the orthonormal basis, which is quite prevalent in Linear time invariant (LTI) systems and common in various applications. This means that the output signals will not change with time and are functions of one another. We also have exponential e-vectors, and the spectral theorem indicates that the sinusoids are Euclidean vectors of LTI systems (All but one dimension is 0). The smooth signals have sparse Fourier representation. Many signals aren't smooth though. The signals with discontinuities have lots of bandwidth. 

In an LTI, a system T that maps input x to output y is linear if 

T(Axa + Bxb) = AT(xa) + BT(xb)

A time invariant system is defined by if the time shift operator σ has the same effect whether or not we apply it to t denoted as 

σ(T(x)) = T(σ(x))

The images we care about (i.e., natural images) are highly compressible if we find a suitable transformed basis where the redundant dimensions are easily identified.

Let's do an example problem. Suppose I have a camera and I take a picture while my hand is shaking. There will be a 2D convolution between X and some convolutional kernel h, which is denoted h * x or 

The measurements are further contaminated by noise

yn1,n2 = {h * x}n1, n2 + zn1, n2. Now the question of the day is how would I measure the unknown image x. 

Convolution is a linear operator where h * x can be expressed as a matrix vector product. We then have a linear inverse problem y = Hx + z where H is the matrix, and we can try many different things with sparsity equations. One way is to assume that x is sparse with some transport  Ψ meaning that x = Ψθ with sparse θ. We can estimate θ using a variety of algorithms then, after that. These are just a few ways in which we can apply real-world applications to deblur an image.