Exploiting matrix structure in optimization for data science

This thesis explores the idea of exploiting matrix structure approximation to improve optimization efficiency in data science from two perspectives:

• Solving the matrix nearness problem to approximate matrix structure;
• Reducing computation costs in optimization through matrix structure approximation.

From the first perspective, we address matrix rank structure approximation by formulating and solving various matrix nearness problems with rank constraints. Our key contributions include matrix approximation with off-block-diagonal rank constraints and extension of symmetric positive definite (SPD)-preserving heuristics to a greedy hierarchical off-diagonal low-rank (HODLR) matrix approximation method.

The practical optimization problems considered in this thesis focus on parameter and hyperparameter estimation of kernel-regularized finite impulse response (FIR) system identification. We have improved the computation efficiency of optimization by simultaneously exploiting existing matrix structure and applying derivative-free optimization methods, iterative methods, randomization and preconditioning. The proposed methodology is matrix-free and scalable. To further improve hyperparameter optimization, we have investigated the use of Bayesian optimization as a global, derivative-free optimization strategy, and we reject hyperparameter points of high degrees of freedom from the optimization procedure. In practice, the point rejection is performed using adaptive matrix structure approximation. We have implemented and tested the methodology with experiments for some commonly used kernels such as tuned correlated (TC), diagonal correlated (DC), and stable spline (SS) kernels in system identification. The results show that the computation time with our methodology scaled approximately linearly with the model order.

In addition, we have proposed an alternative problem formulation of hyperparameter optimization that numerically eliminates a hyperparameter variable to reduce the dimensionality of optimization. Our results show that the hyperparameter optimization with the new formulation finds an optimal solution with fewer objective function evaluations.

This thesis contributes to a further understanding of the matrix structures and the matrix structure approximation, as well as their practical applications to the FIR impulse response estimations.