Timezone: »
Poster
Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Norm
Qinqing Zheng · Ryota Tomioka
We consider the problem of recovering a low-rank tensor from its noisy observation. Previous work has shown a recovery guarantee with signal to noise ratio $O(n^{\ceil{K/2}/2})$ for recovering a $K$th order rank one tensor of size $n\times \cdots \times n$ by recursive unfolding. In this paper, we first improve this bound to $O(n^{K/4})$ by a much simpler approach, but with a more careful analysis. Then we propose a new norm called the \textit{subspace} norm, which is based on the Kronecker products of factors obtained by the proposed simple estimator. The imposed Kronecker structure allows us to show a nearly ideal $O(\sqrt{n}+\sqrt{H^{K-1}})$ bound, in which the parameter $H$ controls the blend from the non-convex estimator to mode-wise nuclear norm minimization. Furthermore, we empirically demonstrate that the subspace norm achieves the nearly ideal denoising performance even with $H=O(1)$.
Author Information
Qinqing Zheng (University of Chicago)
Ryota Tomioka (Microsoft Research Cambridge)
More from the Same Authors
-
2020 Poster: On the Loss Landscape of Adversarial Training: Identifying Challenges and How to Overcome Them »
Chen Liu · Mathieu Salzmann · Tao Lin · Ryota Tomioka · Sabine Süsstrunk -
2019 Poster: Continuous Hierarchical Representations with Poincaré Variational Auto-Encoders »
Emile Mathieu · Charline Le Lan · Chris J. Maddison · Ryota Tomioka · Yee Whye Teh -
2017 Poster: QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding »
Dan Alistarh · Demjan Grubic · Jerry Li · Ryota Tomioka · Milan Vojnovic -
2017 Spotlight: Communication-Efficient Stochastic Gradient Descent, with Applications to Neural Networks »
Dan Alistarh · Demjan Grubic · Jerry Li · Ryota Tomioka · Milan Vojnovic -
2016 Poster: f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization »
Sebastian Nowozin · Botond Cseke · Ryota Tomioka -
2015 Poster: A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements »
Qinqing Zheng · John Lafferty -
2014 Poster: Multitask learning meets tensor factorization: task imputation via convex optimization »
Kishan Wimalawarne · Masashi Sugiyama · Ryota Tomioka -
2013 Poster: Convex Tensor Decomposition via Structured Schatten Norm Regularization »
Ryota Tomioka · Taiji Suzuki -
2012 Poster: Perfect Dimensionality Recovery by Variational Bayesian PCA »
Shinichi Nakajima · Ryota Tomioka · Masashi Sugiyama · S. Derin Babacan -
2011 Poster: Statistical Performance of Convex Tensor Decomposition »
Ryota Tomioka · Taiji Suzuki · Kohei Hayashi · Hisashi Kashima -
2010 Spotlight: Global Analytic Solution for Variational Bayesian Matrix Factorization »
Shinichi Nakajima · Masashi Sugiyama · Ryota Tomioka -
2010 Poster: Global Analytic Solution for Variational Bayesian Matrix Factorization »
Shinichi Nakajima · Masashi Sugiyama · Ryota Tomioka -
2007 Spotlight: Invariant Common Spatial Patterns: Alleviating Nonstationarities in Brain-Computer Interfacing »
Benjamin Blankertz · Motoaki Kawanabe · Ryota Tomioka · Friederike Hohlefeld · Vadim Nikulin · Klaus-Robert Müller -
2007 Poster: Invariant Common Spatial Patterns: Alleviating Nonstationarities in Brain-Computer Interfacing »
Benjamin Blankertz · Motoaki Kawanabe · Ryota Tomioka · Friederike Hohlefeld · Vadim Nikulin · Klaus-Robert Müller -
2006 Poster: Logistic Regression for Single Trial EEG Classification »
Ryota Tomioka · Kazuyuki Aihara · Klaus-Robert Müller -
2006 Spotlight: Logistic Regression for Single Trial EEG Classification »
Ryota Tomioka · Kazuyuki Aihara · Klaus-Robert Müller