Browsing by Subject "Matrix completion"

Now showing 1 - 5 of 5

Large scale matrix factorization with guarantees: sampling and bi-linearity
(2015-12) Bhojanapalli, Venkata Sesha Pavana Srinadh; Sanghavi, Sujay Rajendra, 1979-; Caramanis, Constantine; Dhillon, Inderjit; Dimakis, Alexandros; Ravikumar, Pradeep; Ward, Rachel
Low rank matrix factorization is an important step in many high dimensional machine learning algorithms. Traditional algorithms for factorization do not scale well with the growing data sizes and there is a need for faster/scalable algorithms. In this dissertation we explore the following two major themes to design scalable factorization algorithms for the problems: matrix completion, low rank approximation (PCA) and semi-definite optimization. (a) Sampling: We develop the optimal way to sample entries of any matrix while preserving its spectral properties. Using this sparse sketch (set of sampled entries) instead of the entire matrix, gives rise to scalable algorithms with good approximation guarantees. (b) Bi-linear factorization structure: We design algorithms that operate explicitly on the factor space instead on the matrix. While bi-linear structure of the factorization, in general, leads to a non-convex optimization problem, we show that under appropriate conditions they indeed recover the solution for the above problems. Both these techniques (individually or in combination) lead to algorithms with lower computational complexity and memory usage. Finally we extend these ideas of sampling and explicit factorization to design algorithms for higher order tensors.
Mining structured matrices in high dimensions
(2016-08) Gunasekar, Suriya; Ghosh, Joydeep; Bovik, Alan C; Caramanis, Constantine; Ravikumar, Pradeep; Sanghavi, Sujay
Structured matrices refer to matrix valued data that are embedded in an inherent lower dimensional manifold with smaller degrees of freedom compared to the ambient or observed dimensions. Such hidden (or latent) structures allow for statistically consistent estimation in high dimensional settings, wherein the number of observations is much smaller than the number of parameters to be estimated. This dissertation makes significant contributions to statistical models, algorithms, and applications of structured matrix estimation in high dimensional settings. The proposed estimators and algorithms are motivated by and evaluated on applications in e--commerce, healthcare, and neuroscience. In the first line of contributions, substantial generalizations of existing results are derived for a widely studied problem of matrix completion. Tractable estimators with strong statistical guarantees are developed for matrix completion under (a) generalized observation models subsuming heterogeneous data--types, such as count, binary, etc., and heterogeneous noise models beyond additive Gaussian, (b) general structural constraints beyond low rank assumptions, and (c) collective estimation from multiple sources of data. The second line of contributions focuses on the algorithmic and application specific ideas for generalized structured matrix estimation. Two specific applications of structured matrix estimation are discussed: (a) a constrained latent factor estimation framework that extends the ideas and techniques hitherto discussed, and applies them for the task of learning clinically relevant phenotypes from Electronic Health Records (EHRs), and (b) a novel, efficient, and highly generalized algorithm for collaborative learning to rank (LETOR) applications.
Provable alternating minimization for non-convex learning problems
(2014-08) Netrapalli, Praneeth Kumar; Sanghavi, Sujay Rajendra, 1979-
Alternating minimization (AltMin) is a generic term for a widely popular approach in non-convex learning: often, it is possible to partition the variables into two (or more) sets, so that the problem is convex/tractable in one set if the other is held fixed (and vice versa). This allows for alternating between optimally updating one set of variables, and then the other. AltMin methods typically do not have associated global consistency guarantees; even though they are empirically observed to perform better than methods (e.g. based on convex optimization) that do have guarantees. In this thesis, we obtain rigorous performance guarantees for AltMin in three statistical learning settings: low rank matrix completion, phase retrieval and learning sparsely-used dictionaries. The overarching theme behind our results consists of two parts: (i) devising new initialization procedures (as opposed to doing so randomly, as is typical), and (ii) establishing exponential local convergence from this initialization. Our work shows that the pursuit of statistical guarantees can yield algorithmic improvements (initialization in our case) that perform better in practice.
Reconstructing the connectome from an ensemble of measurements
(2016-05) Morales, Isaiah Steven; Huk, Alexander C.; Harris, Kristen M.; Golding, Nace L.
While connectomics paradigms have been undergoing rapid development in the experimental community, the problem of analyzing the resulting data has remained largely unaddressed. Recently, the mesoscale connectome of the mouse was made available from the Allen Brain Institute. This connectome was constructed by way of using enhanced green fluorescent protein (EGFP) expressing adeno-associated viral vectors to discover the connectivity strength between brain areas. Herein, we will attempt to show that the problem of discovering removed entries from connectivity data in a large neural system from an ensemble of such measurements can be formulated naturally in terms of nuclear norm minimization techniques. It is our belief that the presented methods will allow the acquisition of future connectomes with an order of magnitude reduction in experimental effort, as well as significantly outperform the simpler inference techniques used in prior work, and function well with few data observations.
Statistical analysis for modeling dyadic interactions using machine learning methods
(2017-05) Chiang, Kai-Yang; Dhillon, Inderjit S.; Grauman, Kristen; Niekum, Scott; Hsieh, Cho-Jui
Modeling dyadic interactions between entities is one of the fundamental problems in machine learning with many real-world applications, including recommender systems, data clustering, social network analysis and ranking. In this dissertation, we introduce several improved models for modeling dyadic interactions in machine learning by taking advantage of sophisticated information from different sources, such as prior structure, domain knowledge and side information. We start with exploiting different types of auxiliary information for several motivating applications, including signed link prediction, signed graph clustering, and dyadic rank aggregation. We then further move from an application-specific aspect to a general modeling aspect, where we aim to jointly exploit prior knowledge, problem structure and side information for learning low-rank modeling matrices from missing and corrupted observations. Such a modeling approach provides a general treatment to better model dyadic interactions in various machine learning applications. More importantly, we provide comprehensive theoretical analyses and performance guarantees to help us understand the utility of the additional information and quantify the merits of the proposed methods. These results therefore demonstrate the effectiveness of proposed approaches under both practical and theoretical aspects.