Expansions and factorizations of matrices and their applications

Abstract

Linear algebra is a foundation to decompositions and algorithms for extracting simple structures from complex data. In this thesis, we investigate and apply modern techniques from linear algebra to solve problems arising in signal processing and computer science. In particular, we focus on data that takes the shape of a matrix and we explore how to represent it as products of circulant and diagonal matrices. To this end, we study matrix decompositions, approximations, and structured matrix expansions whose elements are products of circulant and diagonal matrices. Computationally, we develop a matrix expansion with DCD matrices for approximating a given matrix. Remarkably, DCD matrices, i.e., a product of diagonal matrix, circulant matrix, and another diagonal matrix, give an natural extension to rank-one matrices. Inspired from the singular value decomposition, we introduce a notion of a matrix rank closely related to the expansion and compute the rank of some specific structured matrices. Specifically, Toeplitz matrix is a sum of two DCD matrices. Here, we present a greedy algorithmic framework to devise the expansion numerically. Finally, we show that the practical uses of the DCD expansion can be complemented by the proposed framework and perform two experiments with a view towards applications.