More Like this

1. 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
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. Beyond the Signs: Nonparametric tensor completion via sign series.

   Lee, Chanwoo; Wang, Miaoyan (December 2021, 2021 Advances in Neural Information Processing Systems 34 (NeurIPS))

   We consider the problem of tensor estimation from noisy observations with possibly missing entries. A nonparametric approach to tensor completion is developed based on a new model which we coin as sign representable tensors. The model represents the signal tensor of interest using a series of structured sign tensors. Unlike earlier methods, the sign series representation effectively addresses both low- and high-rank signals, while encompassing many existing tensor models— including CP models, Tucker models, single index models, structured tensors with repeating entries—as special cases. We provably reduce the tensor estimation problem to a series of structured classification tasks, and we develop a learning reduction machinery to empower existing low-rank tensor algorithms for more challenging high-rank estimation. Excess risk bounds, estimation errors, and sample complexities are established. We demonstrate the outperformance of our approach over previous methods on two datasets, one on human brain connectivity networks and the other on topic data mining. 

   more » « less
4. Truncated Matrix Completion - An Empirical Study

   https://doi.org/10.23919/EUSIPCO55093.2022.9909952  

   Naik, Rishhabh; Trivedi, Nisarg; Tarzanagh, Davoud Ataee; Balzano, Laura (January 2022, European Signal Processing Conference)

   Low-rank Matrix Completion (LRMC) describes the problem where we wish to recover missing entries of partially observed low-rank matrix. Most existing matrix completion work deals with sampling procedures that are independent of the underlying data values. While this assumption allows the derivation of nice theoretical guarantees, it seldom holds in real-world applications. In this paper, we consider various settings where the sampling mask is dependent on the underlying data values, motivated by applications in sensing, sequential decision-making, and recommender systems. Through a series of experiments, we study and compare the performance of various LRMC algorithms that were originally successful for data-independent sampling patterns. 

   more » « less
5. Additive Error Guarantees for Weighted Low Rank Approximation

   Bhaskara, Aditya; Ruwanpathirana, Aravinda K.; Wijewardena, Maheshakya (January 2021, Proceedings of the 38th International Conference on Machine Learning)

   Low-rank approximation is a classic tool in data analysis, where the goal is to approximate a matrix A with a low-rank matrix L so as to minimize the error ||A-L||_F. However in many applications, approximating some entries is more important than others, which leads to the weighted low rank approximation problem. However, the addition of weights makes the low-rank approximation problem intractable. Thus many works have obtained efficient algorithms under additional structural assumptions on the weight matrix (such as low rank, and appropriate block structure). We study a natural greedy algorithm for weighted low rank approximation and develop a simple condition under which it yields bi-criteria approximation up to a small additive factor in the error. The algorithm involves iteratively computing the top singular vector of an appropriately varying matrix, and is thus easy to implement at scale. Our methods also allow us to study the problem of low rank approximation under L_p norm error. 

   more » « less