- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Polynomial-time tensor decomposition with sum-of-squares
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Polynomial-time tensor decomposition with sum-of-squares Steurer, David
Description
Tensor decomposition is at the heart of many computational problems that arise in machine learning and other kinds of data analyses. However, unlike for matrices, it is NP-hard to compute good decompositions for higher-order tensors. Nevertheless, a sequence of results shows that under simple mild assumptions on the instances good tensor decompositions can be found in polynomial time. I will present a recent framework for tensor decompositon based on the sum-of-squares method that unifies and extends these results. As a consequence, we obtain the first polynomial-time algorithm to decompose overcomplete 4-tensors in the smoothed analysis settings even in the presence of a polynomial amount of noise. Based on a joint work with Tengyu Ma and Jonathan Shi (to appear at FOCS 2016).
Item Metadata
| Title |
Polynomial-time tensor decomposition with sum-of-squares
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2016-09-06T10:15
|
| Description |
Tensor decomposition is at the heart of many computational problems that arise in machine learning and other kinds of data analyses.
However, unlike for matrices, it is NP-hard to compute good decompositions for higher-order tensors.
Nevertheless, a sequence of results shows that under simple mild assumptions on the instances good tensor decompositions can be found in polynomial time.
I will present a recent framework for tensor decompositon based on the sum-of-squares method that unifies and extends these results.
As a consequence, we obtain the first polynomial-time algorithm to decompose overcomplete 4-tensors in the smoothed analysis settings even in the presence of a polynomial amount of noise.
Based on a joint work with Tengyu Ma and Jonathan Shi (to appear at FOCS 2016).
|
| Extent |
52 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Cornell University
|
| Series | |
| Date Available |
2017-03-07
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0343096
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International