\section{Models and assumptions \label{subsec:Models-and-assumptions}}

In this paper, we shall consider a setting with random sampling and
independent random noise as follows.

\begin{assumption}[Random sampling]\label{assumption:random-sampling}Suppose
that $\Omega$ is a symmetric index set.\footnote{This means that if $(i,j,k)\in\Omega$, then $(j,i,k)$, $(i,k,j)$,
$(j,k,i)$, $(k,i,j)$, $(k,j,i)$ are all in $\Omega$.} Assume that each $(i,j,k)$ with $i\leq j\leq k$ is included in
$\Omega$ independently with probability $p$. Throughout this paper,
we shall define
\begin{equation}
\chi_{i,j,k}:=\ind\{(i,j,k)\in\Omega\},\qquad1\leq i,j,k\leq d.\label{eq:def:chi}
\end{equation}
 \end{assumption}

\begin{assumption}[Random noise]\label{assumption:random-noise}Suppose
that $\bm{E}=[E_{i,j,k}]_{1\leq i,j,k\leq d}$ is a symmetric tensor.\footnote{This means that $E_{i,j,k}=E_{j,i,k}=E_{i,k,j}=E_{j,k,i}=E_{k,i,j}=E_{k,j,i}$
for any $1\leq i,j,k\leq d$.} Assume that the noise components $\{E_{i,j,k}\}_{1\leq i\leq j\leq k\leq d}$
are independent sub-Gaussian random variables satisfying $\mathbb{E}[E_{i,j,k}]=0$
and $\mathsf{Var}(E_{i,j,k})=\sigma_{i,j,k}^{2}$. Denoting $\sigma_{\min}:=\min_{i,j,k}\sigma_{i,j,k}$
and $\sigma_{\max}:=\max_{i,j,k}\sigma_{i,j,k}$, we assume throughout
that $\sigma_{\max}/\sigma_{\min}=O(1)$.\end{assumption}

Next, we introduce additional parameters about the unknown tensor
of interest. Recall that 
\[
\bm{T}^{\star}=\sum_{l=1}^{r}\bm{u}_{l}^{\star}\otimes\bm{u}_{l}^{\star}\otimes\bm{u}_{l}^{\star}=\sum_{l=1}^{r}\bm{u}_{l}^{\star\otimes3}\in\mathbb{R}^{d\times d\times d}.
\]
To begin with, we define the strength of each rank-one tensor component
as follows
\begin{equation}
\lambda_{\min}^{\star}:=\min_{1\leq l\leq r}\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{3}\qquad\text{and}\qquad\lambda_{\max}^{\star}:=\max_{1\leq l\leq r}\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{3},\label{eq:defn-lambda-max-min}
\end{equation}
allowing us to define the condition number by
\begin{equation}
\kappa:=\lambda_{\max}^{\star}/\lambda_{\min}^{\star}.\label{eq:defn-cond-number}
\end{equation}
To enable reliable tensor completion, we impose further assumptions
on the tensor factors $\{\bm{u}_{l}^{\star}\}$ as follows.

\begin{assumption}[Incoherence and well-conditionedness]\label{assumption:incoherence}Suppose
that $\bm{T}^{\star}$ satisfies\begin{subequations}\label{eq:incoh}
\begin{align}
\left\Vert \bm{T}^{\star}\right\Vert _{\infty} & \leq\sqrt{\frac{\mu_{0}}{d^{3}}}\,\left\Vert \bm{T}^{\star}\right\Vert _{\mathrm{F}};\label{assumption:T-inf-norm}\\
\left\Vert \bm{u}_{l}^{\star}\right\Vert _{\infty} & \leq\sqrt{\frac{\mu_{1}}{d}}\,\left\Vert \bm{u}_{l}^{\star}\right\Vert _{\mathrm{2}},\qquad1\leq l\leq r;\label{assumption:u-inf-norm}\\
\left|\left\langle \bm{u}_{l}^{\star},\,\bm{u}_{j}^{\star}\right\rangle \right| & \leq\sqrt{\frac{\mu_{2}}{d}}\,\left\Vert \bm{u}_{l}^{\star}\right\Vert _{\mathrm{2}}\left\Vert \bm{u}_{j}^{\star}\right\Vert _{\mathrm{2}},\qquad1\leq l\neq j\leq r.\label{assumption:u-inner-prod}
\end{align}
\end{subequations}Further, assume that $\bm{T}^{\star}$ is well-conditioned
in the sense that $\kappa$ (cf.~(\ref{eq:defn-cond-number})) satisfies
$\kappa=O\left(1\right)$.\end{assumption}

Informally, when both $\mu_{0}$ and $\mu_{1}$ are small, the $\ell_{2}$
energy of both $\bm{T}^{\star}$ and $\bm{u}_{l}^{\star}$ ($1\leq l\leq r$)
is dispersed more or less evenly across their entries. In addition,
a small $\mu_{2}$ necessarily implies that every pair of the tensor
factors of interest is nearly orthogonal to (and hence incoherent
with) each other. Finally, the well-conditionedness assumption guarantees
that no single tensor component has significantly higher energy compared
to the rest of them. For the sake of notational simplicity, we shall
combine them into a single incoherence parameter
\begin{equation}
\mu:=\max\left\{ \mu_{0},\,\mu_{1},\,\mu_{2}\right\} .\label{eq:defn-mu}
\end{equation}

The focal point of this paper lies in obtaining distributional characterization
of, and uncertainty assessment for, the nonconvex estimate (i.e.~the
solution $\bm{U}$ returned by Algorithm \ref{alg:gd}) in a strong
entrywise sense. In particular, we set out the goal to

\begin{itemize}

\item[1)]establish distributional representation of the estimate
$\bm{U}$;

\item[2)]construct short yet valid confidence intervals for each
entry of the tensor factor $\{\bm{u}_{l}^{\star}\}_{1\leq l\leq r}$
as well as each entry of the unknown tensor $\bm{T}^{\star}$.

\end{itemize} 

To cast the latter task in more precise terms: given any target coverage
level $0<1-\alpha<1$, any $1\leq l\leq r$ and any $1\leq i,j,k\leq d$,
the aim is to compute intervals $[c_{1,u},c_{2,u}]$ and $[c_{1,T},c_{2,T}]$
such that\begin{subequations}
\begin{align}
\mathbb{P}\left\{ u_{l,i}^{\star}\in[c_{1,u},c_{2,u}]\right\}  & =1-\alpha+o\left(1\right)\qquad(\text{up to global permutation});\label{eq:CI-tensor-factor}\\
\mathbb{P}\left\{ T_{i,j,k}^{\star}\in[c_{1,T},c_{2,T}]\right\}  & =1-\alpha+o\left(1\right).\label{eq:CI-tensor-entry}
\end{align}
\end{subequations}Here, (\ref{eq:CI-tensor-factor}) is phrased accounting
for global permutation, since one cannot possibly distinguish $\{\bm{u}_{l}^{\star}\}_{1\leq l\leq r}$
and any permutation of them given only the observations (\ref{eq:observed-T}).
Ideally, the above tasks should be accomplished in a data-driven manner
without requiring prior knowledge about the noise distributions.
{"config": "arxiv", "file": "2006.08580/problem.tex"}