Construction of approximately equiangular tight frames and their applications

Abstract

Frames are onsidered a natural extension of orthonormal bases to overomplete spanningsystems. Én the signal proessing ommunity, frames have mainly beome populardue to wavelets; however, many other frame families have been employed in numerousappliations, inluding soure oding, robust transmission, ode division multiple aess(CDMA) systems, and oding theory. The most important harateristi of frames isredundany, whih adds more exibility to signal expansions, failitating various signalproessing tasks.A nite frame with N vetors in an m-dimensional Hilbert spae Hmis usually identi-ed with the m × N matrix F = [f1 f2 : : : fN ], m ≤ N, with olumns the frame vetorsfk ∈ Hm, k = 1; : : : ; N. The most important properties of frames are mutual ohereneand spetral norm. Mutual oherene is a measure of the maximal orrelation betweenthe frame vetors and haraterizes the degree of similarity between the olumns of thematrix F . Spetral norm measures how muh a frame an dilate a unit norm oeÆientvetor. Mutual oherene and spetral norm dene partiular lasses of frames. Unitnorm tight frames (UNTFs) attain optimal bounds of spetral norm; these frames haveunit norm olumns and orthogonal rows of equal norm. Unit norm tight frames with smallmutual oherene are referred to as inoherent UNTFs. The minimum possible mutualoherene is attained by equiangular tight frames (ETFs). The frame vetors of ETFsexhibit idential orrelation and these frames are onsidered losest to orthonormal bases.ETFs oer erasure-robust transmission in ommuniations and minimize interuserinterferene when employed as spreading sequenes in multiuser ommuniation systems.Due to their inoherene, they are of interest in sparse representations and ompressedsensing. However, ETFs do not exist for all frame dimensions and their onstrution hasbeen proved extremely diÆult.This thesis presents two methods that produe real frames lose to ETFs. The proposedonstrutions are motivated by spei appliations, namely, ompressed sensingand sparse representations. Conerning sparse or ompressible signals, that is, signalswith a few signiant oeÆients, ompressed sensing and sparse representations have experiened a growing interest in the last deade, providing the ability of ompat representationsthat serve various data soures. The mathematial model lying in the heart ofthese appliations involves an underdetermined linear system with more unknowns thanequations. Computing its sparsest solution, i.e., the one with the fewest non-vanishingoeÆients is tratable with numerial methods. Standard numerial solvers inlude OrthogonalMathing Pursuit (OMP) and Basis Pursuit (BP).In sparse and redundant representations, we seek a sparse signal representation withrespet to a redundant (overomplete) ditionary. Performane guarantees for the algorithmsdeployed to ompute the non-vanishing oeÆients require that the given ditionaryforms an inoherent UNTF. While many inoherent ditionaries are known in theliterature, their limited sparsifying ability has promoted the design of learning based di-tionaries. Often, learning based ditionaries do not satisfy the neessary properties fornumerial omputations.Compressed sensing is a sampling theory that allows signal reonstrution from aninomplete number of measurements. Conerning signals that are sparse or ompressible,ompressed sensing uses a sensing mehanism implemented by an appropriate matrix, theso-alled projetion matrix. Aording to theoretial results, the projetion matrix mustpossess a property known as the restrited isometry property (RIP). Construting RIPmatries is diÆult, as evaluation of RIP is ombinatorially omplex. Random Gaussianor Bernoulli matries satisfy RIP with high probability. Considering N-dimensional signalswith s non-vanishing oeÆients, reovery onditions for random matries requireO(s log N) measurements. More reent results formulate similar reovery guarantees forprojetion matries that form inoherent UNTFs. Thus, a new design strategy involvesthe onstrution of projetion matries exhibiting small mutual oherene and spetralnorm.Minimum bounds of mutual oherene and spetral norm are attained by ETFs; therefore,the methods proposed here aim at the onstrution of frames as lose to ETFs aspossible. The rst method uses results from frame theory and relies on alternating projetion ideas. The produed onstrutions form UNTFs with remarkably small mutualoherene, that is, inoherent UNTFs. The seond method relies on reent results showingthat there is one-to-one orrespondene of ETFs to a speial type of graphs. The existeneof an ETF is determined by the so-alled signature matrix. A signature matrix has theform of the adjaeny matrix of a graph and its spetrum onsists of two distint eigenvalues.Viewing the onstrution of a signature matrix as an inverse eigenvalue problem,we develop a numerial algorithm to ompute a solution that approximates the signaturematrix of an ETF. The seond method produes nearly equiangular, nearly tight frames,that is, frames with similar olumn orrelation and approximately optimal spetral norm.The proposed frame onstrutions are employed as projetion matries in ompressedsensing, improving substantially the performane of the deployed algorithms in sparsereovery. Considering that many signals are sparse or ompressible under overompleteditionaries, inoherent UNTFs are also used for the design of optimized projetion matries with respet to a given representation ditionary. An additional way to employ theproposed frames to solve underdetermined linear systems is the tehnique of preonditioning.Applying preonditioning to sparse representations, we improve the performane ofthe algorithms deployed to nd the oeÆients of the sparse signal. In ompressed sensing,preonditioning is used to improve signal reovery when binary matries are used asprojetion matries. Note that binary matries are onsidered more suitable for hardwareimplementation.Besides ompressed sensing and sparse representations, one of the proposed onstru-tions has been employed in the design of near-optimal odes or spreading sequenes insynhronous CDMA systems. Optimal spreading sequenes maximize the rate at whihthe users an transmit and minimize interuser interferene. Equal norm tight frames havebeen proved optimal, if all users in the system are ative. When the number of usershanges, the only frames that an minimize interuser interferene are ETFs. However,only a few ETF onstrutions are known in the literature. The near optimal odebookpresented here has the form of a nearly equiangular, nearly tight frame and minimizesinteruser interferene even when some users in the system are silent.