A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion

By Raghunandan H. Keshavan, Sewoong Oh. arXiv.org, 2009

412 citations recorded by the source corpus.

Missing and suspicious traffic data are inevitable due to detector and communication malfunctions, which adversely affect the transportation management system (TMS). In this paper, a tensor pattern which is an extension of matrix is introduced into modeling the traffic data for the first time, which can give full play to traffic spatial–temporal information and preserve the multi-way nature of traffic data. To estimate the missing value, a tensor decomposition based Imputation method has been developed. This approach not only inherits the advantages of imputation methods based on matrix pattern for estimating missing points, but also well mines the multi-dimensional inherent correlation of traffic data. Experiments demonstrate that the proposed method achieves a better imputation performance than the state-of-the-art imputation approach even when the missing ratio is up to 90%. Furthermore, the experimental results show that the proposed method can address the extreme case where the data of one or several days are completely missing, and additionally it can be employed to recover the missing traffic data in adverse weather as well.

Subfields: Building and Construction, Computational Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/fecdca829c0d0e2a21ab9700c28ce87354137051

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Building and Construction

1. Lijun Sun
2. Xinyu Chen
3. Tianyi Zhou
4. Dacheng Tao
5. Zhaocheng He
6. Yuebiao Li
7. Zhiheng Li
8. Li Li

In Computational Mathematics

1. Lijun Sun
2. Xinyu Chen
3. Dacheng Tao
4. Tianyi Zhou
5. Andrea Montanari
6. Yin Zhang
7. Yuebiao Li
8. Zaiwen Wen

In Computer Networks and Communications

1. Wotao Yin
2. Dacheng Tao
3. Tianyi Zhou
4. Andrea Montanari
5. Zaiwen Wen
6. Lijun Sun
7. Yin Zhang
8. Xinyu Chen

Citations in the corpus

• Recommender Systems (2012, background): “We refer readers to [176–180] and the references therein for details.”
• Matrix Completion from Noisy Entries (2009, methodology): “(NeE) = X 0S 0YT 0 ; 3: Minimize Fe(X,Y ) through gradient descent, with initial condition (X 0,Y 0). We may note here that the rank of the matrix M, if not known, can be reliably estimated from NeE (Keshavan and Oh, 2009). The various steps of the above algorithm are defined as follows. Trimming. We”
• GoDec: Randomized Lowrank & Sparse Matrix Decomposition in Noisy Case (2011, methodology): “Compared with the published results (Keshavan & Oh, 2009) of the popular matrix completion methods, e.g., OptSpace, SVT, FPCA and AD- MIRA, GoDec requires both less computational time and less samples to recover a low-rank matrix.”
• CSDI: Conditional Score-based Diffusion Models for Probabilistic Time Series Imputation (2021, background): “These time series data often contain missing values due to various reasons, including device failures and human errors [1, 2, 3].”
• Efficient missing data imputing for traffic flow by considering temporal and spatial dependence (2013, methodology): “From the viewpoint of modeling philosophy, we can roughly divide these methods into three kinds: prediction based, interpolation based and statistical learning based methods (Qu et al., 2009; Tan et al., 2013).”
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm (2012, methodology): “The code OptSpace, which has a C version that was used in our tests, solves a model closely related to (1.4) using a gradient descent approach and starting from a specially constructed initial guess.”
• A Bayesian tensor decomposition approach for spatiotemporal traffic data imputation (2019, positive): “Recently, factorization-based approaches—in particular tensor decomposition—have attracted more and more attention and have been tested in many empirical works (e.g., Qu et al., 2009; Asif et al., 2013b; Li et al., 2013; Tan et al., 2013; Asif et al., 2016; Goulart et al., 2017).”
• Generalized Low Rank Models (2014, methodology): “For example, there are variants on alternating minimization (with alternating least squares as a special case) [37, 158, 141, 35, 36], alternating Newton methods [53, 129], (stochastic or incremental) gradient descent [75, 88, 104, 119, 10, 159, 118], conjugate gradients [120, 134], expectation mini”
• Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition (2013, methodology): “3, by applying our models in both synthetic and real datasets.”
• Traffic state estimation on highway: A comprehensive survey (2017, methodology): “Tensor-based methods using Tucker decomposition (TD) (Tan et al., 2013) have also been used”