Oral Prelim: Kam Chung Wong, Estimation in High-dimensional Vector Autoregressive Models with Noisy And Corrupted Data

Vector Autoregression (VAR) is a widely used method for learning complex relationship among components of multiple time series. Over the years, it has gained popularity in the fields of control theory, statistics, economics, finance, genetics and neuroscience. To estimate the VAR models in a highdimensional setting, where both the number of components of the time series and the order of the model are allowed to grow with sample size, we have to impose structural assumptions on the transition matrices; in particular, we will consider sparsity. Lasso program is a natural relaxation to the NP-hard L0 regularization problem. There are numerous theoretical and empirical results on the Lasso problem, but very limited when it comes to dependent data. In particular, we are interested in estimation of high dimensional VAR models with missing and corrupted data\\
Because of rank deficiency, the Hermitian matrix X'X is non-convex. Moreover, due to the presence of noise and/or missing data, the objective function is indefinite. Along the lines of the modified Lasso framework proposed by Loh and Wainwright (2012), we can show similar results, but with relaxation of a key and stringent assumption that the operator norm of the transition matrix is smaller than 1. On the statistical side, we provide non-asymptotic error bounds for the L1-LS estimators. On the computational side, we will show that projected gradient descent algorithm converges geometrically to L1 estimate. Both guarantees require us to establish validity for Restricted Eigenvalue (RE) and Deviation Bound assumptions for a non-convex design matrix. Interestingly, along with other applications, the same set of assumptions open the door to showing similar computational guarantees under a direct approach
--- L0-regularized estimation.