While multilinear algebra appears natural for studying the multiway
interactions modeled by hypergraphs, tensor methods for general hypergraphs
have been stymied by theoretical and practical barriers. A recently proposed
adjacency tensor is applicable to nonuniform hypergraphs, but is prohibitively
costly to form and analyze in practice. We develop tensor times same vector
(TTSV) algorithms for this tensor which improve complexity from $O(n^r)$ to a
low-degree polynomial in $r$, where $n$ is the number of vertices and $r$ is
the maximum hyperedge size. Our algorithms are implicit, avoiding formation of
the order $r$ adjacency tensor. We demonstrate the flexibility and utility of
our approach in practice by developing tensor-based hypergraph centrality and
clustering algorithms. We also show these tensor measures offer complementary
information to analogous graph-reduction approaches on data, and are also able
to detect higher-order structure that many existing matrix-based approaches
provably cannot.

通过开发 TTST 算法，本文提出了可以改善门坎效应的高维数据处理方法，特别针对研究高维关系模型的超图。

非均匀超图的可伸缩张量方法

Scalable tensor methods for nonuniform hypergraphs

Estimating the joint probability mass function (PMF) of a set of random
variables lies at the heart of statistical learning and signal processing.
Without structural assumptions, such as modeling the variables as a Markov
chain, tree, or other graphical model, joint PMF estimation is often considered
mission impossible - the number of unknowns grows exponentially with the number
of variables. But who gives us the structural model? Is there a generic,
`non-parametric' way to control joint PMF complexity without relying on a
priori structural assumptions regarding the underlying probability model? Is it
possible to discover the operational structure without biasing the analysis up
front? What if we only observe random subsets of the variables, can we still
reliably estimate the joint PMF of all? This paper shows, perhaps surprisingly,
that if the joint PMF of any three variables can be estimated, then the joint
PMF of all the variables can be provably recovered under relatively mild
conditions. The result is reminiscent of Kolmogorov's extension theorem -
consistent specification of lower-dimensional distributions induces a unique
probability measure for the entire process. The difference is that for
processes of limited complexity (rank of the high-dimensional PMF) it is
possible to obtain complete characterization from only three-dimensional
distributions. In fact not all three-dimensional PMFs are needed; and under
more stringent conditions even two-dimensional will do. Exploiting multilinear
algebra, this paper proves that such higher-dimensional PMF completion can be
guaranteed - several pertinent identifiability results are derived. It also
provides a practical and efficient algorithm to carry out the recovery task.
Judiciously designed simulations and real-data experiments on movie
recommendation and data classification are presented to showcase the
effectiveness of the approach.

本文介绍了一种使用多线性代数方法实现关键点之间联合概率质量函数估计的方法，并给出了用于实现复杂度有限的高维概率的完整特征的证明和几个相关的可识别性结果。

有限字母随机向量的张量、学习和 Kolmogorov 扩展

Tensors, Learning, and 'Kolmogorov Extension' for Finite-alphabet Random  Vectors

During the last years, low-rank tensor approximation has been established as
a new tool in scientific computing to address large-scale linear and
multilinear algebra problems, which would be intractable by classical
techniques. This survey attempts to give a literature overview of current
developments in this area, with an emphasis on function-related tensors.

本文为当前低秩张量逼近方法在科学计算中应用的文献综述，着重介绍与函数相关的张量。

低秩张量逼近技术的文献调查

A literature survey of low-rank tensor approximation techniques

We present a spectral theory of hypergraphs that closely parallels Spectral
Graph Theory. A number of recent developments building upon classical work has
led to a rich understanding of "hyperdeterminants" of hypermatrices, a.k.a.
multidimensional arrays. Hyperdeterminants share many properties with
determinants, but the context of multilinear algebra is substantially more
complicated than the linear algebra required to address Spectral Graph Theory
(i.e., ordinary matrices). Nonetheless, it is possible to define eigenvalues of
a hypermatrix via its characteristic polynomial as well as variationally. We
apply this notion to the "adjacency hypermatrix" of a uniform hypergraph, and
prove a number of natural analogues of basic results in Spectral Graph Theory.
Open problems abound, and we present a number of directions for further study.

本论文提出了一个与谱图理论密切相关的超图谱理论，其中应用了多维数组的 “超行列式” 概念，并应用其到均匀超图的 “邻接超矩阵” 中，证明了谱图理论基本结果的自然类比。