Randomized techniques for matrix decomposition and estimating the approximate rank of a matrix

Abstract

Finding low dimensional matrix approximations of the data is an essential task in data analysis and scientific computing. Recently, several randomization schemes have been demonstrated for performing these low-rank matrix approximations. This thesis, reviews some of the randomization techniques for matrix decomposition. It also gives a brief introduction to a similar concept in signal processing called Compressed Sensing.Estimating the approximate (low) rank of the input data matrix is essential to apply these randomized techniques to find the low-rank matrix approximations. There are many other applications in mathematical modeling and rank related problems, where estimating an approximate rank of a matrix is useful. In this thesis, two novel, efficient and computationally inexpensive techniques to find the approximate rank of a matrix are proposed and some applications where these techniques can be used are discussed.The randomized techniques for matrix decomposition, requires generating and storing a large number of random numbers which could have practical complications, when the input matrix is of very large size. Here in this thesis, we demonstrate how matricesffrom Error Control Coding can be used in place of the random matrices in randomization techniques for matrix decomposition and compressed sensing. These matrices are very easy to generate and either deterministic or partially random in nature.