Accelerating Online CP Decompositions for Higher Order Tensors
published: Sept. 27, 2016, recorded: August 2016, views: 1474
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Tensors are a natural representation for multidimensional data. In recent years, CANDECOMP/PARAFAC (CP) decomposition, one of the most popular tools for analyzing multi-way data, has been extensively studied and widely applied. However, today’s datasets are often dynamically changing over time. Tracking the CP decomposition for such dynamic tensors is a crucial but challenging task, due to the large scale of the tensor and the velocity of new data arriving. Traditional techniques, such as Alternating Least Squares (ALS), cannot be directly applied to this problem because of their poor scalability in terms of time and memory. Additionally, existing online approaches have only partially addressed this problem and can only be deployed on third-order tensors. To ﬁll this gap, we propose an efﬁcient online algorithm that can incrementally track the CP decompositions of dynamic tensors with an arbitrary number of dimensions. In terms of eﬀectiveness, our algorithm demonstrates comparable results with the most accurate algorithm, ALS, whilst being computationally much more eﬃcient. Speciﬁcally, on small and moderate datasets, our approach is tens to hundreds of times faster than ALS, while for large-scale datasets, the speedup can be more than 3,000 times. Compared to other state-of-the-art online approaches, our method shows not only signiﬁcantly better decomposition quality, but also better performance in terms of stability, eﬃciency and scalability.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !