Callahan, MatthewVu, TrungRaich, Raviv2025-04-232025-04-232025-04Callahan, Matthew, Trung Vu, and Raviv Raich. “On Momentum Acceleration for Randomized Coordinate Descent in Matrix Completion.” In ICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 1–5, 2025. https://doi.org/10.1109/ICASSP49660.2025.10888539.https://doi.org/10.1109/ICASSP49660.2025.10888539http://hdl.handle.net/11603/38104 ICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)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.5 pagesen-USThis item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.matrix completionrandomized methodsMachine learningRecommender systemsShapeSignal processingComputational complexitySignal processing algorithmsComputational efficiencycoordinate descentSpeech processingasymptotic convergence analysisConvergenceClosed-form solutionsText