A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
We prove that the classic approximation guarantee for the higher-order singular value decomposition (HOSVD) is tight by constructing a tensor for which HOSVD achieves an approximation ratio of $N/(1+\varepsilon)$, for any $\varepsilon > 0$. This matches the upper bound of De Lathauwer et al. (2000a) and shows that the approximation ratio of HOSVD cannot be improved. Using a more advanced construction, we also prove that the approximation guarantees for the ST-HOSVD algorithm of Vannieuwenhoven et al. (2012) and higher-order orthogonal iteration (HOOI) of De Lathauwer et al. (2000b) are tight by showing that they can achieve their worst-case approximation ratio of $N / (1 + \varepsilon)$, for any $\varepsilon > 0$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Lower Bounds for Higher-Order Convex Optimization
State-of-the-art methods in convex and non-convex optimization employ higher-order derivative information, either implicitly or explicitly. We explore the limitations of higher-order optimization and prove that even for …
Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
We give nearly-tight upper and lower bounds for the improving multi-armed bandits problem. An instance of this problem has $k$ arms, each of whose reward function is a concave and increasing function of the number of tim…
Multi-Armed BanditsA Tale of Two Approximations: Tightening Over-Approximation for DNN Robustness Verification via Under-Approximation
The robustness of deep neural networks (DNNs) is crucial to the hosting system's reliability and security. Formal verification has been demonstrated to be effective in providing provable robustness guarantees. To improve…
Stochastic Continuous Greedy ++: When Upper and Lower Bounds Match
In this paper, we develop \scg~(\text{SCG}{$++$}), the first efficient variant of a conditional gradient method for maximizing a continuous submodular function subject to a convex constraint. Concretely, for a monotone …
Inaccuracy matters: accounting for solution accuracy in event-triggered nonlinear model predictive control
We consider the effect of using approximate system predictions in event-triggered control schemes. Such approximations may result from using numerical transcription methods for solving continuous-time optimal control pro…
Model Predictive Control