Random Projection Algorithms For Nonnegative Kronecker Product Least Squares Problems

Now we are facing the time of big data, and how to process data fast and effective-ly is ubiquitous. Randomized matrix algorithm is one of the effective methodology to process data, which has been a hot research area in numerical linear algebra. The data in real world is usually nonnegative, such as image and text data. Nonnegative Kro-necker product least squares problem has been introduced for nonnegative data and has many applications. In this thesis, we will propose randomized projection algorithms to solve nonnegative Kronecker product least squares problem fast and effectively. The pro-posed algorithms will utilize the structure of the coefficient matrix A(?)B in nonnegative Kronecker product least squares problem, and are fast because of subsample randomized Hadamard transform. For different sizes of the matrix A and B, we will devise two dif-ferent type algorithms. In the first type algorithm, if only one of A and B is large scale, we only implement one subsample randomized Hadamard transform to the large scale one. While for the two large scale matrices A and B, we will apply subsample random-ized Hadamard transform to A and B simultaneously. Based on random matrix theory, we will prove the approximated optimal value of nonnegative Kronecker product least squares problem by randomized projection algorithms can give an ?-relative error for the true optimal value with high probability. Numerical experiments show the effectiveness and fastness of the proposed algorithms.