| Summary: | Data processing is a key ingredient in many disciplines such as image and signal processing, machine learning and data mining. Today, as the data size increases exponentially and massive volumes of data are collected, processing this data is becoming more challenging. This leads to an on-going interest in algorithms that are capable to deal efficiently with large datasets. This thesis investigates low rank methods and how they can be utilized in modern data analysis applications. The idea behind successful low rank methods is the fact that in many cases there are dependencies and redundancies within the data. Therefore, the data can be well approximated and processed by utilizing its low rank property which results in a faster processing of smaller data. In this part, an algorithm for efficient object tracking in videos using particle filter is presented. The algorithm uses matrix decomposition methods applied to a Gaussian kernel with a low numerical rank, to select the most representative particles of the probability density function (PDF). Then, a multi-scale function extension method is applied to obtain a fast restoration of the PDF. Another important tool that uses a low rank assumption is matrix completion. Matrix completion algorithms try to complete a matrix with missing entries by minimizing its nuclear norm. In this part, a new and robust algorithm is presented. This algorithm extends the ability of a matrix completion algorithm to deal with a variety of constraints such as the spectral and weighted nuclear norms. Another algorithm presented is a randomized algorithm for low rank LU decomposition. The randomized LU decomposition algorithm has the following advantages: It is faster than other randomized algorithms, parallelizable and consumes low memory as most of it can be done in place and has an efficient capability to process sparse matrices. The last algorithm presented in this thesis is related to the pseudo polar Fourier transform (PPFT), which is an important tool in many applications such as computerized tomography. We present a new algorithm that inverts the 3D pseudo polar Fourier transform. Its accuracy to machine precision is guaranteed within a fixed number of steps. In addition, it has low memory requirements enabling to process large 3D datasets.
|
|---|