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, XRay 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 nonorthogonal 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 nonorthogonal
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 offdiagonal 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 cosparse 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 cosparse analysis operator.
[error in script]
Actions (login required)

View Item 