More Like this

1. Streaming Tensor Factorization for Infinite Data Streams

   https://doi.org/10.1137/1.9781611975321.10  

   Shaden Smith, Kejun Huang (April 2018, SIAM International Conference on Data Mining)

   Sparse tensor factorization is a popular tool in multi-way data analysis and is used in applications such as cybersecurity, recommender systems, and social network analysis. In many of these applications, the tensor is not known a priori and instead arrives in a streaming fashion for a potentially unbounded amount of time. Existing approaches for streaming sparse tensors are not practical for unbounded streaming because they rely on maintaining the full factorization of the data, which grows linearly with time. In this work, we present CP-stream, an algorithm for streaming factorization in the model of the canonical polyadic decomposition which does not grow linearly in time or space, and is thus practical for long-term streaming. Additionally, CP-stream incorporates user-specified constraints such as non-negativity which aid in the stability and interpretability of the factorization. An evaluation of CP-stream demonstrates that it converges faster than state-of-the-art streaming algorithms while achieving lower reconstruction error by an order of magnitude. We also evaluate it on real-world sparse datasets and demonstrate its usability in both network traffic analysis and discussion tracking. Our evaluation uses exclusively public datasets and our source code is released to the public as part of SPLATT, an open source high-performance tensor factorization toolkit. 

   more » « less
2. Fast and low-memory compressive sensing algorithms for low tucker-rank tensor approximation from streamed measurements

   https://doi.org/10.1007/s11075-025-02101-0  

   Haselby, Cullen; Iwen, Mark_A; Needell, Deanna; Rebrova, Elizaveta; Swartworth, William (May 2025, Numerical Algorithms)

   Abstract In this paper we consider the problem of recovering a low-rank Tucker approximation to a massive tensor based solely on structured random compressive measurements (i.e., a sketch). Crucially, the proposed random measurement ensembles are both designed to be compactly represented (i.e., low-memory), and can also be efficiently computed in one-pass over the tensor. Thus, the proposed compressive sensing approach may be used to produce a low-rank factorization of a huge tensor that is too large to store in memory with a total memory footprint on the order of the much smaller desired low-rank factorization. In addition, the compressive sensing recovery algorithm itself (which takes the compressive measurements as input, and then outputs a low-rank factorization) also runs in a time which principally depends only on the size of the sought factorization, making its runtime sub-linear in the size of the large tensor one is approximating. Finally, unlike prior works related to (streaming) algorithms for low-rank tensor approximation from such compressive measurements, we present a unified analysis of both Kronecker and Khatri-Rao structured measurement ensembles culminating in error guarantees comparing the error of our recovery algorithm’s approximation of the input tensor to the best possible low-rank Tucker approximation error achievable for the tensor by any possible algorithm. We further include an empirical study of the proposed approach that verifies our theoretical findings and explores various trade-offs of parameters of interest. 

   more » « less
3. 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
4. Rank-Based Tensor Factorization for Student Performance Prediction

   Doan, T.N.; Sahebi, S. (January 2019, 12th International Conference on Educational Data Mining (EDM))

   One of the essential problems, in educational data mining, is to predict students' performance on future learning materials, such as problems, assignments, and quizzes. Pioneer algorithms for predicting student performance mostly rely on two sources of information: students' past performance, and learning materials' domain knowledge model. The domain knowledge model, traditionally curated by domain experts maps learning materials to concepts, topics, or knowledge components that are presented in them. However, creating a domain model by manually labeling the learning material can be a difficult and time-consuming task. In this paper, we propose a tensor factorization model for student performance prediction that does not rely on a predefined domain model. Our proposed algorithm models student knowledge as a soft membership of latent concepts. It also represents the knowledge acquisition process with an added rank-based constraint in the tensor factorization objective function. Our experiments show that the proposed model outperforms state-of-the-art algorithms in predicting student performance in two real-world datasets, and is robust to hyper-parameters. 

   more » « less
5. Scalable Kernel Density Estimation-based Local Outlier Detection over Large Data Streams

   Qin, X.; Cao, L.; Rundensteiner, EA.; and Madden, S. (March 2019, Proceedings of the 22nd International Conference on Extending Database Technology (EDBT))

   Local outlier techniques are known to be effective for detecting outliers in skewed data, where subsets of the data exhibit diverse distribution properties. However, existing methods are not well equipped to support modern high-velocity data streams due to the high complexity of the detection algorithms and their volatility to data updates. To tackle these shortcomings, we propose local outlier semantics that operate at an abstraction level by leveraging kernel density estimation (KDE) to effectively detect local outliers from streaming data. A strategy to continuously detect top-N KDE-based local outliers over streams is designed, called KELOS – the first linear time complexity streaming local outlier detection approach. The first innovation of KELOS is the abstract kernel center-based KDE (aKDE) strategy. aKDE accurately yet efficiently estimates the data density at each point – essential for local outlier detection. This is based on the observation that a cluster of points close to each other tend to have a similar influence on a target point’s density estimation when used as kernel centers. These points thus can be represented by one abstract kernel center. Next, the KELOS’s inlier pruning strategy early prunes points that have no chance to become top-N outliers. This empowers KELOS to skip the computation of their data density and of the outlier status for every data point. Together aKDE and the inlier pruning strategy eliminate the performance bottleneck of streaming local outlier detection. The experimental evaluation demonstrates that KELOS is up to 6 orders of magnitude faster than existing solutions, while being highly effective in detecting local outliers from streaming data. 

   more » « less