Abstract |
In the first part of this talk, we consider low rank matrix completion problem, which has wide applications such as collaborative filtering, image inpainting and Microarray data imputation.In particular, we present an efficient and scalable algorithm for matrix completion. In each iteration, we pursue a rank-one matrix basis generated by the top singular vector pair of the current approximation residual and update the weights for all rank-one matrices obtained up to the current iteration. We further propose a novel weight updating rule to reduce the time and storage complexity, making the proposed algorithm scalable to large matrices. We establish a linear rate of convergence for the algorithm. Numerical experiments on many real-world large scale datasets demonstrate that our algorithm is much more efficient than the state-of-the-art algorithms while achieving similar or better prediction performance. In the second part we consider the problem of estimating multiple graphical models simultaneously using the fused lasso penalty, which encourages adjacent graphs to share similar structures. A motivating example is the analysis of brain networks of Alzheimer's disease, which involves estimating a brain network for the normal controls (NC), a brain network for the patients with mild cognitive impairment (MCI), and a brain network for Alzheimer's patients (AD). We expect the two brain networks for NC and MCI and for MCI and AD to share common structures but not to be identical to each other. We establish a necessary and sufficient condition for the graphs to be decomposable. As a consequence, a simple but effective screening rule is proposed, which decomposes large graphs into small subgraphs and dramatically reduces the overall computational cost. Numerical experiments on both synthetic and real data demonstrate the effectiveness and efficiency of the proposed approach. |