Globally optimal representations of low-complexity models: statistical guarantees and algorithms

To seek a low-dimension representation for high-dimension data has always been one of the very fundamental tasks in various areas such as machine learning, signal processing, and statistics. This thesis focuses on the theoretical constructive algorithm in recovering the low-complexity representation of high-dimension data. We first focus a unique sparse representation of the $mb Y$ that satisfies the following generative model $mb Y=mb Amb X$ where $mb Ain bb{R}^{pimes r}$ is a deterministic latent factor and $mb Xin bb{R}^{rimes n}$ is an unknown sparse matrix. We prove that this low-rank, sparse decomposition of $mb Y$ can be uniquely identified,up to some intrinsic signed permutation. Our approach relies on solving a non-convex optimization problem constrained over the unit sphere. Our geometric analysis for its non-convex optimization landscape showsthat any strict local solution is close to the ground truth, and can be recovered by a simple data-driveninitialization followed with any second-order descent algorithm. par We then turn to the varimax Vintage factor analysis which is one important type of factor analysis that aims to first find a low-dimensional representation of the original data, and then to seek a varimax rotation such that the rotated low-dimensional representation is scientifically meaningful. Despite its popularity, little theoretical guarantee can be provided mainly because varimax rotation requires to solve a non-convex optimization over the set of orthogonal matrices. To solve this, we propose a deflation varimax procedure that resolves each row of an orthogonal matrix sequentially and adopt this as the second step after the PCA (Principal Component Analysis) procedure.Our analysis to this two-fold procedure display it estimates the factor loading matrix in the optimal rate when the signal-to-noise-ratio (SNR) is moderate or large despite the intrinsic non-convexity for the procedure.par We further explore community detection problem in contextual networks, a well-known task that aims to represent data by leveraging its intrinsic low-complexity structure. We begin by decomposing the model into signal and noise components within a probabilistic framework, referred to as Contextual Label Stochastic Block Model (CLSBM) . Next, we establish a theoretical lower bound for the optimal misclassification rate. Additionally, we propose an efficient algorithm with theoretical guarantees to consistently recover the label for each node in the network.