Matrix completion plays an important role in machine learning and signal processing, with applications ranging from recommender systems to image inpainting. Many approaches have been considered to solve the problem and some offer computationally efficient solutions. In particular, a highly-efficient random coordinate descent approach reduces the per-epoch computation dramatically. This paper is concerned with further improvement of computational efficiency to expand the range of problem sizes and conditions that can be solved. Momentum acceleration is a well-known method to improve the efficiency of iterative algorithms, but applying it to random coordinate descent methods without increasing the computational complexity is non-trivial. To address this challenge, we introduce a momentum-accelerated randomized coordinate descent for matrix completion approach that does not increase computational complexity by accelerating at the level of epochs. Additionally, we propose an analysis-driven, tuning-free method for step size selection. To that end, we offer a convergence rate analysis for the algorithm. Using numerical evaluations, we demonstrate the competitiveness of the method and verify the theoretical analysis.

Low-rank matrix completion, the process of estimating a low-rank matrix from a small subset of its entries, has many applications including collaborative filtering and system identification. Many algorithms have been considered to address this problem. Coordinate descent has been previously proposed to tackle scalability both in terms of runtime and space complexity. Due to the use of regularization in the method, the method provides no convergence guarantees. Additionally, the choice of the regularization parameter can significantly affect the algorithm performance. Here, we study a regularization-free randomized coordinate descent method that uses an efficient periodic refactorization to guarantee a linear convergence rate. To support the proposed algorithm, we provide an analysis of the algorithm asymptotic convergence rate alongside a per-iteration computational complexity analysis. Using numerical experiments, we verify the correctness of our analysis and illustrate the overall computation advantage of the proposed approach.

Joint blind source separation (JBSS) is a powerful framework for extracting latent sources from multiple datasets while keeping their coherence across multiple linked datasets. Algorithms for JBSS, while offering the capability of improved estimation performance, often incur high computational complexity and hence are not scalable to studies with hundreds or thousands of datasets. In this paper, we propose a simple yet efficient method for source separation that exploits both the correlation among sources within each dataset and across the datasets. The proposed method, named reference-guided component analysis (RGCA), uses source templates as references to (i) guide the separation of sources on each dataset and (ii) establish source dependence and automatically align them across the datasets. In addition, we promote independence among latent sources within each dataset by adding orthogonal constraints on the demixing vectors. The resulting optimization admits an analytic solution that enables extremely fast implementation of RGCA. Our numerical results demonstrate that RGCA obtains competitive performance while having a runtime far superior to other JBSS methods. The proposed method provides a robust and scalable solution to multi-subject functional magnetic resonance imaging (fMRI) studies, enabling joint analysis of thousands of subjects within a few minutes.

Subgroup identification is a fundamental step in precision medicine. Recent research applying data-driven methods such as independent component/vector analysis to multi-subject functional magnetic resonance imaging (fMRI) data has effectively revealed meaningful subgroups. These methods typically focus on single-dimensional information, such as individual functional networks or assuming uniform subgroup structures across networks. Given the complex nature of psychiatric disorders, considering the relationships among subjects across different functional networks can offer valuable insights into diagnostic heterogeneity. We introduce a novel subgroup identification method that leverages multiplex community detection to identify subgroups from multi-subject resting-state fMRI data. The proposed method models subject correlations across functional networks as a multiplex network and identifies common communities across multiple networks and unique communities specific to each functional network. Results from applying the proposed method to 464 psychotic patients show that the identified subgroups exhibit significant group differences on multiple meaningful functional networks as well as the clinical scores, which demonstrate the effectiveness of our method on identifying meaningful subgroups.

Factorization-based gradient descent is a scalable and efficient algorithm for solving low-rank matrix completion. Recent progress in structured non-convex optimization has offered global convergence guarantees for gradient descent under certain statistical assumptions on the low-rank matrix and the sampling set. However, while the theory suggests gradient descent enjoys fast linear convergence to a global solution of the problem, the universal nature of the bounding technique prevents it from obtaining an accurate estimate of the rate of convergence. This paper performs a local analysis of the exact linear convergence rate of gradient descent for factorization-based symmetric matrix completion. Without any additional assumptions on the underlying model, we identify the deterministic condition for local convergence guarantee for gradient descent, which depends only on the solution matrix and the sampling set. More crucially, our analysis provides a closed-form expression of the asymptotic rate of convergence that matches exactly with the linear convergence observed in practice. To the best of our knowledge, our result is the first one that offers the exact linear convergence rate of gradient descent for matrix factorization in Euclidean space for matrix completion.

Histopathological image analysis is a challenging task due to a diverse histology feature set as well as due to the presence of large non-informative regions in whole slide images. In this paper, we propose a multiple-instance learning (MIL) method for image-level classification as well as for annotating relevant regions in the image. In MIL, a common assumption is that negative bags contain only negative instances while positive bags contain one or more positive instances. This asymmetric assumption may be inappropriate for some application scenarios where negative bags also contain representative negative instances. We introduce a novel symmetric MIL framework associating each instance in a bag with an attribute which can be either negative, positive, or irrelevant. We extend the notion of relevance by introducing control over the number of relevant instances. We develop a probabilistic graphical model that incorporates the aforementioned paradigm and a corresponding computationally efficient inference for learning the model parameters and obtaining an instance level attribute-learning classifier. The effectiveness of the proposed method is evaluated on available histopathology datasets with promising results.

This paper introduces the use of adaptive restart to accelerate iterative hard thresholding (IHT) for low-rank matrix completion. First, we analyze the local convergence of accelerated IHT in the non-convex setting of matrix completion problem (MCP). We prove the linear convergence rate of the accelerated algorithm inside the region near the solution. Our analysis poses a major challenge to parameter selection for accelerated IHT when no prior knowledge of the "local Hessian condition number" is given. To address this issue, we propose a simple adaptive restart algorithm for MCP to recover the optimal rate of convergence at the solution, as motivated in [1]. Our numerical result verifies the theoretical analysis as well as demonstrates the outstanding performance of the proposed algorithm.

We present a momentum-based accelerated iterative hard thresholding (IHT) for low-rank matrix completion. We analyze the convergence of the proposed Heavy Ball (HB) accelerated IHT near the solution and provide optimal step size parameters that guarantee the fastest rate of convergence. Since the optimal step sizes depend on the unknown structure of the solution matrix, we further propose a heuristic for parameter selection that is inspired by recent results in random matrix theory. Our experiment on a simple matrix completion setting verifies our analysis and illustrates the competitive rate of convergence that can be obtained with the proposed algorithm.