Tensor decomposition is a fundamental method used in various areas to deal
with high-dimensional data. \emph{Tensor power method} (TPM) is one of the
widely-used techniques in the decomposition of tensors. This paper presents a
novel tensor power method for decomposing arbitrary order tensors, which
overcomes limitations of existing approaches that are often restricted to
lower-order (less than $3$) tensors or require strong assumptions about the
underlying data structure. We apply sketching method, and we are able to
achieve the running time of $\widetilde{O}(n^{p-1})$, on the power $p$ and
dimension $n$ tensor. We provide a detailed analysis for any $p$-th order
tensor, which is never given in previous works.

本文提出一种新的张量幂法来分解任意阶张量，克服了现有方法的局限性，应用草图方法能够在幂次 p 和维数 n 的张量上实现运行时间的 O ~（n ^ p-1）~ 。

任意阶 Faster Robust Tensor Power Method

Faster Robust Tensor Power Method for Arbitrary Order

A predominant topic in the theory of evolutionary algorithms and, more
generally, theory of randomized black-box optimization techniques is running
time analysis. Running time analysis aims at understanding the performance of a
given heuristic on a given problem by bounding the number of function
evaluations that are needed by the heuristic to identify a solution of a
desired quality. As in general algorithms theory, this running time perspective
is most useful when it is complemented by a meaningful complexity theory that
studies the limits of algorithmic solutions.
In the context of discrete black-box optimization, several black-box
complexity models have been developed to analyze the best possible performance
that a black-box optimization algorithm can achieve on a given problem. The
models differ in the classes of algorithms to which these lower bounds apply.
This way, black-box complexity contributes to a better understanding of how
certain algorithmic choices (such as the amount of memory used by a heuristic,
its selective pressure, or properties of the strategies that it uses to create
new solution candidates) influences performance.
In this chapter we review the different black-box complexity models that have
been proposed in the literature, survey the bounds that have been obtained for
these models, and discuss how the interplay of running time analysis and
black-box complexity can inspire new algorithmic solutions to well-researched
problems in evolutionary computation. We also discuss in this chapter several
interesting open questions for future work.

研究演化算法的理论，尤其是随机黑盒优化技术理论中占主导地位的一个话题是运行时间分析，它旨在通过限制启发式算法在给定问题上需要的函数评估次数来理解其性能，并通过复杂性理论来研究算法解决问题的极限。该论文从黑盒优化的角度回顾了文献中提出的不同的黑盒复杂性模型，并对这些模型的界限进行了调查，探讨了运行时间分析和黑盒复杂性的相互作用如何启发演化计算中已经研究的问题的新算法解决方案，并讨论了未来工作的若干有趣的开放性问题。