We are delighted to announce that Tamara Kolda will give the next One World Mathematics of Information, Data, and Signals (1W-MINDS) Seminar this Thursday, July 23rd, at 2:30 pm EDT (11:30 am Pacific time). Attendees can watch the seminar using the following zoom link at that time:
https://msu.zoom.us/j/99187747781
Dr. Kolda’s title and abstract are below, and can also be found on the seminar website along with information about other upcoming talks, videos of past talks, and more at https://sites.google.com/view/minds-seminar/home
======================================================
Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition
Conventional algorithms for finding low-rank canonical polyadic (CP) tensor decompositions are unwieldy for large sparse tensors. The CP decomposition can be computed by solving a sequence of overdetermined least problems with special Khatri-Rao structure. In this work, we present an application of randomized algorithms to fitting the CP decomposition of sparse tensors, solving a significantly smaller sampled least squares problem at each iteration with probabilistic guarantees on the approximation errors. Prior work has shown that sketching is effective in the dense case, but the prior approach cannot be applied to the sparse case because a fast Johnson-Lindenstrauss transform (e.g., using a fast Fourier transform) must be applied in each mode, causing the sparse tensor to become dense. Instead, we perform sketching through leverage score sampling, crucially relying on the fact that the structure of the Khatri-Rao product allows sampling from overestimates of the leverage scores without forming the full product or the corresponding probabilities. Naive application of leverage score sampling is ineffective because we often have cases where a few scores are quite large, so we propose a novel hybrid of deterministic and random leverage-score sampling which consistently yields improved fits. Numerical results on real-world large-scale tensors show the method is significantly faster than competing methods without sacrificing accuracy. This is joint work with Brett Larsen, Stanford University.
======================================================
Please feel free forward this email to others who may be interested. If this email has been forwarded to you and you’d like to receive your own announcements in the future, you can sign up for them here