More Like this

1. Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow

   Zhang, Xiao; Du, Simon; Gu, Quanquan (July 2018, International Conference on Machine Learning)

   We revisit the inductive matrix completion problem that aims to recover a rank-r matrix with ambient dimension d given n features as the side prior information. The goal is to make use of the known n features to reduce sample and computational complexities. We present and analyze a new gradient-based non-convex optimization algorithm that converges to the true underlying matrix at a linear rate with sample complexity only linearly depending on n and logarithmically depending on d. To the best of our knowledge, all previous algorithms either have a quadratic dependency on the number of features in sample complexity or a sub-linear computational convergence rate. In addition, we provide experiments on both synthetic and real world data to demonstrate the effectiveness of our proposed algorithm. 

   more » « less
2. Grassmannian optimization for online tensor completion and tracking with the t-svd

   https://doi.org/10.1109/TSP.2022.3164837  

   Gilman, Kyle; Tarzanagh, Davoud Ataee; Balzano, Laura (January 2022, IEEE transactions on signal processing)

   We propose a new fast streaming algorithm for the tensor completion problem of imputing missing entries of a lowtubal-rank tensor using the tensor singular value decomposition (t-SVD) algebraic framework. We show the t-SVD is a specialization of the well-studied block-term decomposition for third-order tensors, and we present an algorithm under this model that can track changing free submodules from incomplete streaming 2-D data. The proposed algorithm uses principles from incremental gradient descent on the Grassmann manifold of subspaces to solve the tensor completion problem with linear complexity and constant memory in the number of time samples. We provide a local expected linear convergence result for our algorithm. Our empirical results are competitive in accuracy but much faster in compute time than state-of-the-art tensor completion algorithms on real applications to recover temporal chemo-sensing and MRI data under limited sampling. 

   more » « less
3. On Sinkhorn's Algorithm and Choice Modeling

   Qu, Zhaonan; Galichon, Alfred; Gao, Wenzhi; Ugander, Johan (July 2025, Operations research)

   For a broad class of models widely used in practice for choice and ranking data based on Luce's choice axiom, including the Bradley--Terry--Luce and Plackett--Luce models, we show that the associated maximum likelihood estimation problems are equivalent to a classic matrix balancing problem with target row and column sums. This perspective opens doors between two seemingly unrelated research areas, and allows us to unify existing algorithms in the choice modeling literature as special instances or analogs of Sinkhorn's celebrated algorithm for matrix balancing. We draw inspirations from these connections and resolve some open problems on the study of Sinkhorn's algorithm. We establish the global linear convergence of Sinkhorn's algorithm for non-negative matrices whenever finite scaling matrices exist, and characterize its linear convergence rate in terms of the algebraic connectivity of a weighted bipartite graph. We further derive the sharp asymptotic rate of linear convergence, which generalizes a classic result of Knight (2008). To our knowledge, these are the first quantitative linear convergence results for Sinkhorn's algorithm for general non-negative matrices and positive marginals. Our results highlight the importance of connectivity and orthogonality structures in matrix balancing and Sinkhorn's algorithm, which could be of independent interest. More broadly, the connections we establish in this paper between matrix balancing and choice modeling could also help motivate further transmission of ideas and lead to interesting results in both disciplines. 

   more » « less
4. Online Tensor Completion and Free Submodule Tracking With The T-SVD

   https://doi.org/10.1109/ICASSP40776.2020.9053199  

   Gilman, Kyle; Balzano, Laura (May 2020, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   null (Ed.)

   We propose a new online algorithm, called TOUCAN, forthe tensor completion problem of imputing missing entriesof a low tubal-rank tensor using the tensor-tensor product (t-product) and tensor singular value decomposition (t-SVD) al-gebraic framework. We also demonstrate TOUCAN’s abilityto track changing free submodules from highly incompletestreaming 2-D data. TOUCAN uses principles from incre-mental gradient descent on the Grassmann manifold to solvethe tensor completion problem with linear complexity andconstant memory in the number of time samples. We com-pare our results to state-of-the-art batch tensor completion al-gorithms and matrix completion algorithms. We show our re-sults on real applications to recover temporal MRI data underlimited sampling. 

   more » « less
5. One or two frequencies? The Iterative Filtering answers

   https://doi.org/10.1016/j.amc.2023.128322  

   Cicone, Antonio; Serra-Capizzano, Stefano; Zhou, Haomin (February 2024, Applied Mathematics and Computation)

   The Iterative Filtering method is a technique aimed at the decomposition of non-stationary and non-linear signals into simple oscillatory components. This method, proposed a decade ago as an alternative technique to the Empirical Mode Decomposition, has been used extensively in many applied fields of research and studied, from a mathematical point of view, in several papers published in the last few years. However, even if its convergence and stability are now established both in the continuous and discrete setting, it is still an open problem to understand up to what extent this approach can separate two close-by frequencies contained in a signal. In this paper, first we recall previously discovered theoretical results about Iterative Filtering. Afterward, we prove a few new theorems regarding the ability of this method in separating two nearby frequencies both in the case of continuously and discrete sampled signals. Among them, we prove a theorem which allows to construct filters which captures, up to machine precision, a specific frequency. We run numerical tests to confirm our findings and to compare the performance of Iterative Filtering with the one of Empirical Mode Decomposition and Synchrosqueezing methods. All the results presented confirm the ability of the technique under investigation in addressing the fundamental “one or two frequencies” question. 

   more » « less