Finite frames for sparse representation

Sasmal, Pradip and Sastry, Challa Subrahmanya and Jampana, Phanindra Varma (2017) Finite frames for sparse representation. PhD thesis, Indian institute of technology Hyderabad.

Full text not available from this repository. (Request a copy)

Abstract

Sparse signal processing is a mathematical theory that predicts the possibility of reconstructing the complete informational content of some signals, such as electrocardiograms, X-Ray and MR medical images, from the knowledge of a few samples. The underlying property of these signals is called sparsity, which means the signal of interest admits representation with a very few nonzero coefficients in some transform domain. For the most part, advances in the theory of sparse signal processing have been made assuming sparsity with respect to orthogonal basis [93]. However, research has demonstrated that much higher level of sparsity takes place when the orthogonality property is relaxed [71–73, 160] and non-orthogonal framework (provided by the notion of frames) is adopted [1, 21]. For a finite dimensional Hilbert space, a frame is a finite collection of vectors having the spanning property. In an Euclidean space setting, taking the vectors as columns of a matrix, one may treat a frame as a full rank matrix. The ratio of number of vectors in a frame and the ambient dimension of vectors is called the redundancy of the frame. The redundancy of a frame helps to acquire and transmit data in an efficient way. Throughout the Thesis we have referred the matrix form a frame as a dictionary or simply as a matrix. Sparse signal processing mainly consists of two approaches, namely sparse representation and compressed sensing (CS) [92]. The former deals with representing the already collected data in a parsimonious manner and helps to reduce computational and storage requirements. On the other hand, compressed sensing is the area of research which studies the design of the data sensing system so that only a few linear measurements are acquired by exploiting the fact that the signal of interest lies in a lower dimensional subspace. In spite of differences in the realization of sparsity, sparse signal representation and compressed sensing share a similar mathematical setup. The thesis work centers around extending a few compressed sensing results by considering sparsity within a non-orthogonal framework. The sparse signal recovery problem, in general, is tackled via two classes of methods, namely Greedy (such as the Orthogonal Matching Pursuit (OMP)) and Convex relaxation approaches (such as the Basis Pursuit (BP)) [29]. One of the results embodied in the thesis introduces the rate of convergence, along with error analysis, of a recent greedy approach, called Self Projected Matching Pursuit (SPMP) [160], which is a low memory implementation of OMP. So far there are no available results on numerical error analysis for greedy algorithms. The coherence [9] of a unit norm frame (the maximum off-diagonal element - in magnitude - in the Gram matrix) measures the minimum angle between the frame elements, which plays an important role in establishing theoretical guarantees for the successful recovery of greedy algorithms and basic pursuit. Motivated by the need for frames possessing low coherence (termed as incoherent frames), the current work proposes a convex optimization technique which both analytically and empirically justifies that it is indeed possible to generate incoherent frames from a given frame via preconditioning [188]. Restricted Isometry Property (in short, RIP) [27] of a frame has significance in establishing the equivalence between the classical sparse signal recovery problem and its convex relaxation. The existence of a preconditioner that improves the RIP constant is also discussed in the present work. In spite of random frames satisfying optimal theoretical bounds, the importance of deterministic frames is undeniable. There have been some attempts towards generating new frames from two existing frames via Kronecker product [50]. However, noticing that there is a room to exploit vii the structure of existing binary matrices [91] (whose elements are 0, 1), the thesis proposes a new composition rule and generates a new binary frame of much better aspect ratio from the given binary frames. In addition to the composition rule, which needs two existing frames as input, the current work also provides deterministic construction of frames using design theory [195]. Our construction of structured CS matrices provides better theoretical guarantees than the unstructured ones [9,217]. To this end, the work accomplished generalizes the notion of Euler Squares [193] and presents a new construction procedure. The stated generalization is then used for the construction of deterministic frames of much better aspect ratio. The results described so far pertain to the synthesis model of sparsity. Nevertheless, the co-sparse analysis modeling [130] is a very interesting and emerging direction in sparse representation theory. My future efforts shall be devoted towards investigating the role of a dual frame as a co-sparse analysis operator.

[error in script]

IITH Creators: