Although robust tensor completion has been extensively studied, the effect of incorporating side information has not been explored. In this article, we fill this gap by developing a novel high-order robust tensor completion model that incorporates both latent and explicit side information. We base our model on the transformed t-product because the corresponding tensor tubal rank can characterize the inherent low-rank structure of a tensor. We study the effect of side information on sample complexity and prove that our model needs fewer observations than other tensor recovery methods when side information is perfect. This theoretically shows that informative side information is beneficial for learning. Extensive experimental results on synthetic and real data further demonstrate the superiority of the proposed method over several popular alternatives. In particular, we evaluate the performance of our solution based on two important applications, namely, link prediction in signed networks and rating prediction in recommender systems. We show that the proposed model, which manages to exploit side information in learning, outperforms other methods in the learning of such low-rank tensor data. Furthermore, when dealing with varying dimensions, we also design an online robust tensor completion with side information algorithm and validate its effectiveness using a real-world traffic dataset in the supplementary material. The source code is available athttps://github.com/yyyancy/RTCF.

In this paper, we aim to build a novel bandits algorithm that is capable of fully harnessing the power of multi-dimensional data and the inherent non-linearity of reward functions to provide high-usable and accountable decision-making services. To this end, we introduce a generalized low-rank tensor contextual bandits model in which an action is formed from three feature vectors, and thus is represented by a tensor. In this formulation, the reward is determined through a generalized linear function applied to the inner product of the action’s feature tensor and a fixed but unknown parameter tensor with low-rank structure. To effectively achieve the trade-off between exploration and exploitation, we introduce an algorithm called “Generalized Low-Rank Tensor Exploration Subspace then Refine” (G-LowTESTR). This algorithm first collects data to explore the intrinsic low-rank tensor subspace information embedded in the scenario, and then converts the original problem into a lower-dimensional generalized linear contextual bandits problem. Rigorous theoretical analysis shows that the regret bound of G-LowTESTR is superior to those in vectorization and matricization cases. We conduct a series of synthetic and real data experiments to further highlight the effectiveness of G-LowTESTR, leveraging its ability to capitalize on the low-rank tensor structure for enhanced learning.

Frequent directions (FDs), as a deterministic matrix sketching technique, have been proposed for tackling low-rank approximation problems. This method has a high degree of accuracy and practicality but experiences a lot of computational cost for large-scale data. Several recent works on the randomized version of FDs greatly improve the computational efficiency but unfortunately sacrifice some precision. To remedy such an issue, this article aims to find a more accurate projection subspace to further improve the efficiency and effectiveness of the existing FDs' techniques. Specifically, by utilizing the power of the block Krylov iteration and random projection technique, this article presents a fast and accurate FDs algorithm named r-BKIFD. The rigorous theoretical analysis shows that the proposed r-BKIFD has a comparable error bound with original FDs, and the approximation error can be arbitrarily small when the number of iterations is chosen appropriately. Extensive experimental results on both synthetic and real data further demonstrate the superiority of r-BKIFD over several popular FDs algorithms both in terms of computational efficiency and accuracy.

Low-tubal-rank tensor approximation has been proposed to analyze large-scale and multidimensional data. However, finding such an accurate approximation is challenging in the streaming setting, due to the limited computational resources. To alleviate this issue, this article extends a popular matrix sketching technique, namely, frequent directions (FDs), for constructing an efficient and accurate low-tubal-rank tensor approximation from streaming data based on the tensor singular value decomposition (t-SVD). Specifically, the new algorithm allows the tensor data to be observed slice by slice but only needs to maintain and incrementally update a much smaller sketch, which could capture the principal information of the original tensor. The rigorous theoretical analysis shows that the approximation error of the new algorithm can be arbitrarily small when the sketch size grows linearly. Extensive experimental results on both synthetic and real multidimensional data further reveal the superiority of the proposed algorithm compared with other sketching algorithms for getting low-tubal-rank approximation, in terms of both efficiency and accuracy.

It is known that frequent directions (FD) is a popular deterministic matrix sketching technique for low rank approximation. However, FD and its randomized variants usually meet high computational cost or computational instability in dealing with large-scale datasets, which limits their use in practice. To remedy such issues, this paper aims at improving the efficiency and effectiveness of FD. Specifically, by utilizing the power of Block Krylov Iteration and count sketch techniques, we propose a fast and accurate FD algorithm dubbed as BKICS-FD. We derive the error bound of the proposed BKICS-FD and then carry out extensive numerical experiments to illustrate its superiority over several popular FD algorithms, both in terms of computational speed and accuracy.