Name
Abstract | ||
|---|---|---|
Many problems can be formulated as recovering a low-rank tensor. Although an increasingly common task, tensor recovery remains a challenging problem because of the delicacy associated with the decomposition of higher-order tensors. To overcome these difficulties, existing approaches often proceed by unfolding tensors into matrices and then apply techniques for matrix completion. We show here that such matricization fails to exploit the tensor structure and may lead to suboptimal procedure. More specifically, we investigate a convex optimization approach to tensor completion by directly minimizing a tensor nuclear norm and prove that this leads to an improved sample size requirement. To establish our results, we develop a series of algebraic and probabilistic techniques such as characterization of subdifferential for tensor nuclear norm and concentration inequalities for tensor martingales, which may be of independent interests and could be useful in other tensor-related problems. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10208-015-9269-5 | Foundations of Computational Mathematics |
Keywords | Field | DocType |
Concentration inequality,Convex optimization,Dual certificate,Matrix completion,Nuclear norm minimization,Subdifferential,Tensor completion,Tensor rank,Primary 90C25,Secondary 90C59,15A52 | Mathematical optimization,Tensor,Tensor (intrinsic definition),Matrix completion,Mathematical analysis,Subderivative,Matrix norm,Matricization,Tensor product of Hilbert spaces,Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1405.1773 | 4 | 1615-3375 |
Citations | PageRank | References |
17 | 0.66 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ming Yuan | 1 | 195 | 22.42 |
| Cun-Hui Zhang | 2 | 174 | 18.38 |