Fast Multivariate Spatio-temporal Analysis via Low Rank Tensor Learning
Accurate and efficient analysis of multivariate spatio-temporal data is critical in climatology, geology, and sociology applications. Existing models usually assume simple inter-dependence among variables, space, and time, and are computationally expensive. We propose a unified low rank tensor learning framework for multivariate spatio-temporal analysis, which can conveniently incorporate different properties in spatio-temporal data, such as spatial clustering and shared structure among variables. We demonstrate how the general framework can be applied to cokriging and forecasting tasks, and develop an efficient greedy algorithm to solve the resulting optimization problem with convergence guarantee. We conduct experiments on both synthetic datasets and real application datasets to demonstrate that our method is not only significantly faster than existing methods but also achieves lower estimation error.
The authors consider the task of interpolation (cokriging) and forecasting on spatio-temporal tensor data. They show that both tasks can be posed as a (non-convex) low-rank tensor optimization problem, and proceed to present a learning method that combines a forward greedy selection with an optional orthogonal projection step. Experiments consider simulated data, two climatological datasets, and another containing FourSquare checkins.  I would not consider myself an expert in this particular domain, and am not in a position to comment on novelty or the presented proofs. That said, I find the paper clearly written. The presented greedy approach to low-rank learning seems reasonable, and the experiments show clear gains relative to other methods. In all this seems a solid paper with no obvious faults.Minor Points - While the discussion in 2.1 and 2.2 is easy to follow, it is not obvious to me how equation (4) in section 2.3 is equivalent to equation (1), how  equation (5) is equivalent to (3), and how both (4) and (5) are equivalent to (6). A reference or more verbose explanation in the supplementary material would be helpful.  - When discussing Fig 1c the authors write that the "run time of ADMM increase[s] rapidly with data size while the greedy algorithm stays steady".   This does not seem an accurate representation, as the run time clearly increases for all algorithms. If the longest performed run is indeed only 1000 seconds, then I would encourage the authors to further test the scalability of their algorithm with additional longer runs. - Is the RMSE used to characterize cokriging and forecasting performance normalized in some way? If so, it would be interesting if the authors could provide some insight into why there are comparatively large gains in the CCDS dataset, whereas all algorithms appear to perform well on the Foursquare dataset- Line 34: From machine learning perspective -> From [a] machine learning perspective- Line 305: five folds cross-validation -> five-fold cross-validation