Construction of approximately equiangular tight frames and their applicatios (Doctoral thesis)

Τσιλιγιάννη, Ευαγγελία


Frames are considered a natural extension of orthonormal bases to overcomplete span­ ning systems. In the signal processing community, frames have mainly become popular due to wavelets; however, many other frame families have been employed in numerous applications, including source coding, robust transmission, code division multiple access (CDMA) systems, and coding theory. The most important characteristic of frames is redundancy, which adds more flexibility to signal expansions, facilitating various signal processing tasks, A finite frame with N vectors in an m-dimensional Hilbert space is usually identi­ fied with the m x N matrix F = [/ i f 2 ... / at ], ra < N , with columns the frame vectors f k e Hm, k = The most important properties of frames are mutual coherence and spectral norm. Mutual coherence is a measure of the maximal correlation between the frame vectors and characterizes the degree of similarity between the columns of the matrix F. Spectral norm measures how much a frame can dilate a unit norm coefficient vector. Mutual coherence and spectral norm define particular classes of frames. Unit norm tight frames (UNTFs) attain optimal bounds of spectral norm; these frames have unit norm columns and orthogonal rows of equal norm. Unit norm tight frames with small mutual coherence are referred to as incoherent UNTFs. The minimum possible mutual coherence is attained by equiangular tight frames (ETFs). The frame vectors of ETFs exhibit identical correlation and these frames are considered closest to orthonormal bases, ETFs offer erasure-robust transmission in communications and minimize interuser interference when employed as spreading sequences in multiuser communication systems. Due to their incoherence, they are of interest in sparse representations and compressed sensing. However, ETFs do not exist for all frame dimensions and their construction has been proved extremely difficult. This thesis presents two methods that produce real frames close to ETFs, The pro­ posed constructions are motivated by specific applications, namely, compressed sensing and sparse representations. Concerning sparse or compressible signals, that is, signals with a few significant coefficients, compressed sensing and sparse representations have experienced a growing interest in the last decade, providing the ability of compact repre­ sentations that serve various data sources. The mathematical model lying in the heart of these applications involves an underdetermined linear system with more unknowns than equations. Computing its sparsest solution, i.e,, the one with the fewest non-vanishing coefficients is tractable with numerical methods. Standard numerical solvers include Or­ thogonal Matching Pursuit (OMP) and Basis Pursuit (BP), In sparse and redundant representations, we seek a sparse signal representation with respect to a redundant (overcomplete) dictionary. Performance guarantees for the algo­ rithms deployed to compute the non-vanishing coefficients require that the given dictio­ nary forms an incoherent UNTF, While many incoherent dictionaries are known in the literature, their limited sparsifving ability has promoted the design of learning based dic­ tionaries, Often, learning based dictionaries do not satisfy the necessary properties for numerical computations. Compressed sensing is a sampling theory that allows signal reconstruction from an incomplete number of measurements. Concerning signals that are sparse or compressible, compressed sensing uses a sensing mechanism implemented by an appropriate matrix, the so-called projection matrix. According to theoretical results, the projection matrix must possess a property known as the restricted isometry property (RIP), Constructing RIP matrices is difficult, as evaluation of RIP is combinatorially complex. Random Gaussian or Bernoulli matrices satisfy RIP with high probability. Considering iV-dimensional sig­ nals with s non-vanishing coefficients, recovery conditions for random matrices require O(s logiV) measurements. More recent results formulate similar recovery guarantees for projection matrices that form incoherent UNTFs, Thus, a new design strategy involves the construction of projection matrices exhibiting small mutual coherence and spectral norm. Minimum bounds of mutual coherence and spectral norm are attained by ETFs; there­ fore, the methods proposed here aim at the construction of frames as close to ETFs as possible. The hrst method uses results from frame theory and relies on alternating pro­ jection ideas. The produced constructions form UNTFs with remarkably small mutual coherence, that is, incoherent UNTFs, The second method relies on recent results showing that there is one-to-one correspondence of ETFs to a special type of graphs. The existence of an ETF is determined by the so-called signature matrix. A signature matrix has the form of the adjacency matrix of a graph and its spectrum consists of two distinct eigen­ values, Viewing the construction of a signature matrix as an inverse eigenvalue problem, we develop a numerical algorithm to compute a solution that approximates the signature matrix of an ETF, The second method produces nearly equiangular, nearly tight frames , that is, frames with similar column correlation and approximately optimal spectral norm. The proposed frame constructions are employed as projection matrices in compressed sensing, improving substantially the performance of the deployed algorithms in sparse recovery. Considering that many signals are sparse or compressible under overcomplete dictionaries, incoherent UNTFs are also used for the design of optimized projection matrices with respect to a given representation dictionary. An additional way to employ the proposed frames to solve underdetermined linear systems is the technique of precondition­ ing, Applying preconditioning to sparse representations, we improve the performance of the algorithms deployed to find the coefficients of the sparse signal. In compressed sens­ ing, preconditioning is used to improve signal recovery when binary matrices are used as projection matrices. Note that binary matrices are considered more suitable for hardware implementation. Besides compressed sensing and sparse representations, one of the proposed construc­ tions has been employed in the design of near-optimal codes or spreading sequences in synchronous CDMA systems. Optimal spreading sequences maximize the rate at which the users can transmit and minimize interuser interference. Equal norm tight frames have been proved optimal, if all users in the system are active. When the number of users changes, the only frames that can minimize interuser interference are ETFs, However, only a few ETF constructions are known in the literature. The near optimal codebook presented here has the form of a nearly equiangular, nearly tight frame and minimizes interuser interference even when some users in the system are silent.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Subject classification: Frames (Information theory)
Keywords: Frames,Equiangular tight frames
URI: http://olympias.lib.uoi.gr/jspui/handle/123456789/27755
Appears in Collections:Διδακτορικές Διατριβές

Files in This Item:
File Description SizeFormat 
Δ.Δ. ΤΣΙΛΙΓΙΑΝΝΗ ΕΥΑΓΓΕΛΙΑ 2015.pdf870.33 kBAdobe PDFView/Open



 Please use this identifier to cite or link to this item:
http://olympias.lib.uoi.gr/jspui/handle/123456789/27755
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.