TITLE: How does using a Bell state lead to a $\cos \left(\frac{1}{8}\pi \right)$ probability of winning in the CHSH game?
QUESTION [3 upvotes]: I have trouble understanding how the CHSH (which stands for John Clauser, Michael Horne, Abner Shimony, and Richard Holt) game, as described in this paper (and shortly explained in this post), works.
I understand that $75\%$ is the maximum probability of winning in a classical system.
The following Bell state
$$\frac{\left| 00 \right> + \left| 11 \right>}{\sqrt{2}}$$
can be interpreted as having $50\%$ chance that both qubits are $\left| 0\right>$ and $50\%$ chance that they are both $\left| 1 \right>$.
This state can be prepared using the following gate

However, it is unclear to me how the Bell state (above) leads to a $\cos\left(\frac{1}{8}\pi\right)\approx0.85$ probability of winning in the CHSH game.
I have made a visual representation of the Bloch sphere from one side in Desmos, and I see how a certain angle corresponds to a certain probability. This might be an incorrect interpretation, but this is how I picture a qubit.
So, how does the CHSH game conclude that the probability to 'win' in a quantum system is $\cos(\frac{1}{8}\pi)$, or an angle of $45°$ in my Desmos example?

REPLY [4 votes]: $\newcommand{\ket}[1]{\left|#1\right>}$
Indeed, the story about $\cos\frac{\pi}{8}$, is not told often, except in quantum mechanics lesson, and even there, it is often left as “exercise left to the reader”. This number is not obvious at first sight, but is the result of an optimization and a straightforward application of quantum mechanics computation rules.
What is apparently lacking in your description to find it is the description of the measurements.
To keep things (relatively) simple, I will assume that we deal with single photons entangled in polarization, and I will only consider linear polarization. Let denote by $α$ (rep. $β$) the angle defining Alice’s (resp. Bob’s) measurement. Measuring the polarization of a single photon in a direction $α$, is a binary measurement, giving $0$ if the photon is oriented along $α$, and $1$ if it is oriented along $α+\frac{π}{2}$. Measuring along this direction, is equivalent to first rotate the photon by an angle $-α$, ant then measure it in the vertical-horizontal (a.k.a $α=0$) basis. This rotation is a linear transformation, transforming Alice’s state as follows:
$$\ket{0}:↦\cosα\ket0 - \sinα \ket1$$
$$\ket{1}:↦\sinα\ket0 + \cosα \ket1$$
Bob’s states transform in a similar way, leading, for the global state, to
$$
\frac{\ket{00}+\ket{11}}{\sqrt2}:↦\\(\cosα\cosβ+\sinα\sinβ)\frac{\ket{00}+\ket{11}}{\sqrt2}+(-\cosα\sinβ+\sinα\cosβ)\frac{\ket{01}-\ket{10}}{\sqrt2}$$
To find the optimal measurement for the CHSH game, you need then to optimize over the possible sets of angles $(α,α',β,β')$. Of course, being clever and knowing trigonometric formulæ helps in this optimization. (Knowing that the answer is $(0,\frac{π}{4},\frac{π}{8},\frac{3π}{8})$ helps too !).
Following the habits of the field, I leave the complete computation as an exercise to the reader ;-).
By the way, this only shows that the CHSH game can be won with 85% success rate with quantum entanglement. The fact that one cannot do better  is known as Tsirelson’s bound, and
involves linear algebra.
Footnotes
¹: *If it where more obvious, many discussions on the nature of entanglement might have happened much before the 1960’s *


TITLE: $\rho$-shift in parabolically induced representations
QUESTION [1 upvotes]: In order to define the principal series representations one takes an irreducible, unitary representation $\sigma$ of $M$ (here $G$ is a semisimple Lie group with Iwasawa decomposition $G=KAN$ and $M$ is the centralizer of $A$ in $K$) and a character $\nu\in\mathfrak{a'}_\mathbb{C}$ to obtain an $MA$-representation. One extends trivially to get an $MAN$-module. Now one induces this representation to $G$. However the induced space consists  of functions $f$ that satisfy $f(kman)=e^{-(\nu+\rho)(\log a)}\sigma(m)^{-1}f(k)$.
Why is there a $\rho$-shift and for which reason does one need it?

REPLY [6 votes]: Let $G$ be a Lie group and $H$ a closed subgroup of $G$. In general, the unitarity of a representation of $H$ is not preserved when inducing unless there is a choice of invariant positive density (positive Haar measure) on $G/H$. To avoid this problem, we tensor the original representation with the one-dimensional representation given by the square root of the modular function on $H$, when constructing the induced representation. In other words, if $(\xi, V_\xi)$ is a continuous finite dimensional Hilbert representation of $H$ and if we denote by $\Delta$ the modular function on $H$, then the tensor product representation $(\xi\otimes\Delta^{1/2}, V_\xi\otimes\mathbb{C})$ can be isometrically realised in $V_\xi$ by the representation
$$(\xi\otimes\Delta^{1/2})(h)v = \Delta(h)^{1/2}\xi(h)v\quad \text{for}\, v\in V_\xi, h\in H$$
(Here I have slightly abused the notation). Now we induced from this last representation and we get ${\rm Ind}_H^G(\xi) = {\rm ind}_H^G(\xi\otimes\Delta^{1/2})$ (Note the capital letters). Then ${\rm Ind}_H^G$ is the normalised induced representation.
Answering your question, the principal series representation is $\textbf{normalised}$ parabolic induction with respect to certain characters. Thus, with your $MAN$-module $V_\sigma$ given by $$(\sigma\otimes\nu)(man)v = e^{\nu({\rm log}\, a)}\sigma(m)v$$
you still have to tensor it with the square root of the modular function of $P$. We claim that $\Delta_P(man) = e^{2\rho_P({\rm log}\, a)}$. This means that
$$((\sigma\otimes\nu)\otimes \Delta_P^{1/2})(man) = e^{(\nu + \rho)({\rm log}\, a)}\sigma(m) = (\sigma\otimes(\nu + \rho))(man)\quad\text{for}\, man\in MAN$$
Thus, we observe that normalising comes just about as shifting by $\rho$.
$\textbf{Claim}$: $\Delta_P(man) = e^{2\rho_P({\rm log}\,a)}$.
$\textit{Proof.}$ First of all, since $M$ is compact, $\Delta_P(M) = 1$. Then
$$\Delta_P(an) = \frac{|\det {\rm Ad}(an)|_{\mathfrak{m}\oplus\mathfrak{a}\oplus\mathfrak{n}}|}{|\det {\rm Ad}(an)|} = |\det{\rm Ad}(an)|_{\overline{\mathfrak{n}}}| = |\det{\rm Ad}(a)|_{\overline{\mathfrak{n}}}|^{-1}|\det{\rm Ad}(n)|_{\overline{\mathfrak{n}}}|^{-1}$$
One can also check that ${\rm Ad}(n)$ is a nilpotent map for every $n\in N$, hence the second term of the product is equal to 1. Then we have that
$$\Delta_P(man) = |\det{\rm Ad}(a)|_{\overline{\mathfrak{n}}}|^{-1} = e^{-{\rm tr}(ad({\rm log}\, a)|_{\overline{n}})} = e^{2\rho_P({\rm log}\, a)} $$


TITLE: Cross-ratio projective geometry
QUESTION [0 upvotes]: I have 4 points $P_0=[1:2], P_1=[3:4], P_2=[5:6], P_3=[7,8]$ in $\mathbb KP^1$ and would like to evaluate the cross-ratio.
It is given by the following:
$\pi:\mathbb KP^1\rightarrow G$ is the unique projective map with $\pi([1:0])=P_0, \pi([0:1])=P_1, \pi([1:1])=P_2$ and $\pi([x_0:x_1])=P_3$
The cross-ratio is euqal to $\frac{x_1}{x_0}$
My problem is, how to evaluate $x_0$ and $x_1$, may you could help me with that.

REPLY [1 votes]: Pay attention to the fact that we have
$$P_2\,,\,P_3\in l: [1:2]+t[2:2]=P_0+t(P_1-P_0)$$
as a projective map, $\,\pi\,$ must map collinear points to collinear points...can you take it from here?


text:
\subsection{Improving $S$}
Unlike the proof of Theorem~\ref{thm:exact}, we will first focus on the simple case of improving the core tensor $\ten S$. Note that here we only try to make sure we get close to $\ten T_{1,1,1}$ as the components $\bm A,\bm B, \bm C$ may still be missing directions.
\begin{lemma}
\label{lem:improve_S}
Set $\kappa_0 = \sqrt{\gamma}$.
Assume $R(\tup) < \tau$. Then

\[
\|\ten T_{1,1,1} - \ten S(\bm A_1, \bm B_1, \bm C_1)\|_F > \kappa_0\,\, \Rightarrow\,\, \|\nabla f(\tup)\|_F = \Omega(\gamma^{2.5}).
\]
\end{lemma}
\begin{proof}
Define $\ten S^* = \ten T(\bm A_1^+, \bm B_1^+,\bm C_1^+)$, so that $\ten S^*(\bm A_1,\bm B_1,\bm C_1) = \ten T_{1,1,1}$.
We consider the direction $\Delta \ten S = \ten S^* - \ten S_{1,1,1}$.
Observe that $\Delta \ten S(\bm A, \bm B, \bm C) =\ten T_{1,1,1} - \ten S(\bm A_1, \bm B_1, \bm C_1)$.
We can write
\begin{align*}
\ten S(\bm A, \bm B, \bm C) - \ten T = \sum_{i,j,k \in \{1,2\}} \ten S(\bm A_i, \bm B_j, \bm C_k) - \ten T_{i,j,k},
\end{align*}
and this is a sum of mutually orthogonal tensors.
Hence, the
the first-order perturbation of $L(\ten S + \epsilon \Delta \ten S, \bm A, \bm B, \bm C)$ is
\begin{align*}
 2\langle \point - \ten T, \Delta \ten S(\bm A, \bm B, \bm C) \rangle &= -2 \|\Delta\ten S(\bm A, \bm B,\bm C)\|_F^2.
\end{align*}

The first-order perturbation in the regularizer $\langle \nabla_{\ten S} R, \Delta \ten S\rangle$ is bounded by $O(\tau^{3/4}\sigma^{-3}) = o(\sigma)$, since $\|\ten S^*\|_F = O(\sigma^{-3})$.
Therefore, the decrease in the tensor loss dominates all other first-order perturbations, so we have a viable direction of improvement.
In particular, by moving in direction $\epsilon \Delta \ten S$,
we decrease the objective function by
\[
\epsilon\cdot \Omega(\|\ten T_{1,1,1} - \ten S(\bm A_1, \bm B_2, \bm C_1)\|_F^2) = \Omega(\epsilon\kappa_0^2).
\]
The direction of movement has norm bounded by
\[\|\ten T_{1,1,1}\|_F \|\bm A_1^+\|_2\|\bm B_1^+\|_2\|\bm C_1^+\|_2 \le K\sigma^{-3}.\] By Cauchy-Schwarz, the gradient has norm at least $\Omega(\kappa_0^2)\times \sigma^3 = \Omega(\gamma^{5/2}).$
\end{proof}

\subsection{Adding missing directions}
\label{subsec:missing_dirs}
Finally, we try to add missing directions to $\bm A, \bm B, \bm C$. As before we separate the cases into missing 1, 2 and 3 directions. This first case (missing one direction) is easy as it is a normal saddle point with negative Hessian.
\begin{lemma}
\label{lem:add_1_direction}
Set $\kappa_1 = 2K\sigma^{3/4}$.
Assume $R(\tup) < \tau$ and $\|\bm A_3\|_F$, $\|\bm B_3\|_F$, and $\|\bm C_3\|_F$ are all less than $\gamma$.
If $\|\ten T_{2,1,1}\|_2 \geq \kappa_1$,
then $\nabla^2 f$ has a negative eigenvalue of at most $-\Omega(\sigma^{15/4})$.
\end{lemma}
\begin{proof}
Since $\kappa_1 > 2K\sqrt{\gamma}$, by Lemma \ref{lem:rank_bound}, we have $\text{rank}(\bm A_1) < r$.

By assumption, there exist unit vectors $\bm a \in U_{1,2}$, $\bm b \in U_{2,1}$, and $\bm c \in U_{3,1}$ such that
$\ten T(\bm a,\bm b,\bm c) \geq \kappa_1$.
Take unit vectors $\bm u, \bm v, \bm w \in \mathbb{R}^r$ such that $\bm A_1^\top \bm u = \bm 0$,  $\bm B_1^\top \bm v =  \alpha_1 \bm b$, $\bm B_2^\top \bm v =\bm 0$, $\bm C_1^\top \bm w = \alpha_2 \bm c$, and $\bm C_2^\top \bm w = \bm 0$, where
$\alpha_i \geq \sigma$ for $i=1,2$.
In this situation, we are near a second-order saddle point, so we seek to demonstrate a direction with sufficient negative curvature in the objective function.
To this end, define
\begin{align*}
\Delta \bm A = \sigma \bm u\bm a^\top \qquad \Delta \ten S = \bm u\otimes \bm v\otimes \bm w.
\end{align*}
For a step size $\epsilon > 0$, our source of improvement in the tensor loss comes from the second-order perturbation of $L$ in this direction. We aim to compare the second-order decrease in $L$ against the second-order increases in $L$ and $R$.
The second-order perturbation in the tensor loss $\nabla^2 L$ applied to $(\Delta \ten S, \Delta \bm A, \bm 0, \bm 0)$ is
\[
2\langle \diff, \Delta \ten S(\Delta \bm A, \bm B, \bm C)\rangle + \|\Delta \point + \ten S(\Delta \bm A, \bm B, \bm C)\|^2
\]
The magnitude of \emph{decrease} in this perturbation is given by
\begin{align*}
\langle \ten T,\Delta \ten S(\Delta \bm A, \bm B, \bm C)\rangle &= \sigma\ten T(\bm a,\alpha_1 \bm b , \alpha_2 \bm c )\\
&= \sigma \alpha_1\alpha_2\ten T(\bm a,\bm b,\bm c)\\
&\geq  \sigma \alpha_1\alpha_2\kappa_1.
\end{align*}
To bound the magnitude of the \emph{increase}, observe that
\begin{align*}
\|\bm B\bm B^\top \bm v\|_F &= \| \alpha_1\bm B_1\bm b\|_F \leq \alpha_1K; \quad \|\bm C\bm C^\top \bm w\|_F \leq \alpha_2K
\end{align*}
Then we have
\begin{align}
\langle \point ,\Delta \ten S(\Delta \bm A, \bm B, \bm C)\rangle &= \langle \point, \sigma \bm a \otimes  \bm B^\top \bm v \otimes \bm C^\top \bm w\rangle \nonumber\\
&= \sigma \ten S(\bm A\bm a, \bm B\bm B^\top \bm v, \bm C\bm C^\top \bm w) \nonumber\\
\label{ineq:bound1}
&\leq \sigma^2\alpha_1\alpha_2K^3
\end{align}
Additionally,
\begin{align*}
\|\Delta \point\|_F^2 &= \|\bm A_2^\top \bm u\otimes \alpha_1 \bm b \otimes \alpha_2 \bm c \|_F^2\\
&\leq \sigma^2\alpha_1^2\alpha_2^2\\
\|\ten S_{(1)}^\top \bm u\|_F^2 &= \bm u^\top(\ten S_{(1)}\ten S_{(1)}^\top  - \bm A\bm A^\top )\bm u + \bm u^\top\bm  A\bm A^\top \bm  u\\
&\leq \tau^{1/4} + \sigma^2\\
 \|\ten S(\Delta \bm A,\bm B,\bm C)\|_F^2 &=\sigma^2\|\bm a\bm u^\top \ten S_{(1)}(\bm B \otimes \bm C)\|_F^2\\
&\leq \sigma^2 \|\ten S_{(1)}^\top \bm u\|_F^2\|\bm B\|_F^2\|\bm C\|_F^2\\
&\leq\sigma^2 K^4(\tau^{1/4}+\sigma^2)
\end{align*}
Putting this together, we bound $\| \Delta \point + \ten S( \Delta \bm A, \bm B, \bm C)\|_F^2$ above by
\begin{align}
\label{ineq:bound2}
\left(\sigma\alpha_1\alpha_2 + \sigma K^2\sqrt{\tau^{1/4}+\sigma^2}\right)^2
\end{align}
In light of the definition of $\kappa_1$ and inequalities (\ref{ineq:bound1}) and (\ref{ineq:bound2}), the second-order perturbation in $L$ is $-\Omega(\sigma\alpha_1\alpha_2\kappa_1)$, i.e. $L$ decreases to second-order in this direction.

Now we turn our attention to the regularizer.
We need to show that the second-order increase in the regularizer doesn't overwhelm the decrease in $L$.
Note that the regularizer is degree 4 with respect to $\|\bm A\bm A^\top - \ten S_{(1)}\ten S_{(1)}^\top\|_F$ (and same terms for $\bm B$ and $\bm C$), so the second order derivatives have a quadratic term in $\|\bm A\bm A^\top - \ten S_{(1)}\ten S_{(1)}^\top\|_F$,
which is $O(\tau^{1/4}) = o(\sigma\alpha_1\alpha_2\kappa_1)$; higher-order terms are negligible in comparison.

We've shown that the loss function decreases by at least $\Omega(\sigma\alpha_1\alpha_2\kappa_1)\cdot \epsilon^2$. Since our direction of improvement has constant norm, this implies that $\nabla^2 f$ has an eigenvalue that is smaller than $-\Omega(\sigma\alpha_1\alpha_2\kappa_1) = - \Omega(\sigma^{15/4})$.

\end{proof}

Next, we need to deal with the high order saddle points. Here our main observation is that if we choose directions randomly in the correct subspace, then the perturbation is going to have a reasonable correlation with the residual tensor with constant probability. This is captured by the following anti-concentration property:
\begin{lemma}
\label{lem:anti}
Let $\ten X \in \mathbb{R}^{d_1\times d_2\times d_3}$, and let $\bm a\in\mathbb{R}^{d_1}, \bm b\in\mathbb{R}^{d_2}, \bm c\in\mathbb{R}^{d_3}$ be independent, uniformly distributed unit vectors.  There exist positive numbers $C_1 = \Omega(1/\sqrt{d_1d_2d_3}) = \somega(1), C_2 = \Omega(1)$ such that
\[
\text{Pr}[|\ten X(\bm a,\bm b,\bm c)| \geq C_1\|\ten X\|_F] > C_2.
\]
\end{lemma}
\begin{proof}
Although our Algorithm \ref{alg:add_direction} for sampling missing directions only requires uniform unit vectors (from appropriate subspaces), we construct these vectors as normalized Gaussian vectors for this lemma in order to apply a Gaussian polynomial anti-concentration result (Theorem 8 in \cite{carbery2001distributional}).
As such, let $\bm a', \bm b', \bm c'$ be independent standard Gaussian random vectors (of appropriate dimension) and set $\bm a = \bm a'/\|\bm a'\|_2$, $\bm b = \bm b'/\|\bm b'\|_2$, and $\bm c = \bm c'/\|\bm c'\|_2$.
Note that there exists some constant $p> 0$ such that $\|\bm a'\|_2 \le 2\sqrt{d_1}$, $\|\bm b'\|_2\le 2\sqrt{d_2}$, and $\|\bm c'\| \le  2\sqrt{d_3}$ with probability at least $p$.
Next, note that $\mathbb{E} \ten X(\bm a', \bm b', \bm c') = 0$ and
\begin{align*}
\text{Var}[\ten X(\bm a', \bm b', \bm c')] &= \mathbb{E}(\ten X(\bm a', \bm b', \bm c')^2)\\
&= \mathbb{E}\langle \ten X(\bm a'\bm a'^\top, \bm b'\bm b'^\top, \bm c'\bm c'^\top),\ten X\rangle\\
&= \langle \ten X(\bm I, \bm I, \bm I),\ten X\rangle\\
&= \|\ten X\|_F^2.
\end{align*}
Now $\ten X(\bm a',\bm b',\bm c')/\|\ten X\|_F$ is a degree three polynomial function with unit variance, so the anti-concentration inequality
 implies that for any $\epsilon > 0$,
\begin{align*}
\text{Pr}[|\ten X(\bm a',\bm b',\bm c')/\|\ten X\|_F| \leq \epsilon] \leq O(1)\epsilon^{1/3}.
\end{align*}
Simply choosing a constant $\epsilon$ and re-arranging terms completes the proof.
\end{proof}

Using this idea, when $\ten T_{2,2,1}$ is large, we show how to get a direction of improvement.

\begin{lemma}
\label{lem:add_2_directions}
Set  $\kappa_2 = 2K\sigma^{1/8}$.
Assume $R(\tup) < \tau$ and $\|\bm A_3\|_F$, $\|\bm B_3\|_F$, and $\|\bm C_3\|_F$ are all less than $\gamma$.
Further assume that $\|\ten T_{2,1,1}\|_2$, $\|\ten T_{1,2,1}\|_2$, and $\|\ten T_{1,1,2}\|_2$ are each less than $\kappa_1$.
Let $\bm a, \bm b, \bm c, \bm u, \bm v, \bm w$ be the output of Algorithm \ref{alg:add_direction} given the input $\bm A, \bm B, \bm C, \sigma, (2,2,1)$.
Define the directions $\Delta \bm A = \bm u\bm a^\top$, $\Delta \bm B = \bm v \bm b^\top$, $\Delta \ten S = \bm u \otimes \bm v \otimes \bm w$.
If $\|\ten T_{2,2,1}\|_2 \geq \kappa_2$, then with constant probability, a step in these directions decreases the objective function
by $\Omega^*(\sigma^{15/8})$.
\end{lemma}

\begin{proof}
First, observe that $\kappa_2 \geq 2K\sqrt{\gamma}$, which implies that $\text{rank}(\bm A_1) < r$ and $\text{rank}(\bm B_1)< r$ by Lemma \ref{lem:rank_bound}.
\begin{comment}
Now let $\bm a', \bm b', \bm c'$ be sampled from the standard multivariate Guassian distribution on $U'_{1,2}$, $U'_{2,2}$, and $U'_{3,1}$, respectively, and let $\bm a, \bm b, \bm c$ be the normalized versions of these.
Let $\bm u, \bm v \in \mathbb{R}^r$ be unit vectors
so that $\bm A_1^\top \bm u = 0$ and $\bm B_1^\top \bm v = 0$.
Define $\bm w' = (\bm C_1^\top)^+\bm c$ and $\bm w = \bm w'/\|\bm w'\|$.
\end{comment}
Set $\alpha$ such that $\alpha \bm  c = \bm C_1^\top \bm w$, and note that $\alpha \geq \sigma$.
Per lemma \ref{lem:anti}, with constant probability we have $|\ten T(\bm a,\bm b, \bm c)|$ is with some constant factor of $ \|\ten T_{2,2,1}\|_2$. Therefore, with constant probability,  $|\ten T(\bm a,\bm b, \bm c)| \geq C\kappa_2$ for some positive constant $C$.

Observe that $p(\delta) := f(\ten S+\delta \Delta \ten S, \bm A+\delta \Delta \bm A, \bm B+\delta\Delta \bm B, \bm C)$ defines a degree $8$ polynomial in $\delta$.
Set $\delta = \sigma^{1/4}$.
For convenience, define the following expressions related to the perturbations of $L$:
\begin{align*}
L_0 &= \diff\\
L_1 &= \Delta \point + \ten S(\Delta \bm A, \bm B, \bm C) + \ten S(\bm A,\Delta \bm B, \bm C) \\
L_2 &= \Delta \ten S(\Delta \bm A, \bm B, \bm C) + \Delta \ten S(\bm A,\Delta \bm B, \bm C) +\ten S(\Delta \bm A, \Delta \bm B, \bm C)\\
L_3 &= \Delta\ten S(\Delta\bm A, \Delta\bm B,\bm C)
\end{align*}
We can upper bound each of these terms in norm, e.g.
\begin{align*}
\|L_1\|_F &= \| \bm A^\top \bm u \otimes \bm B^\top \bm v \otimes \bm C^\top \bm w + \ten S(\bm u\bm a^\top,\bm B,\bm C) + \ten S(\bm A,\bm v\bm b^\top,\bm C)\|_F\\
&\leq \sigma^2\alpha + 2K^2\sqrt{\tau^{1/4}+\sigma^2}\\
&= O(\alpha\sigma^2 + \sigma).
\end{align*}
Through similar calculations, we have $\|L_2\|_F = O(\alpha\sigma + \sigma)$ and $\|L_3\|_F = O(\alpha)$.
The perturbation in the tensor loss is then
\begin{equation}
\label{eq:loss_perturb}
\delta^3 \langle  L_0,L_3\rangle + \delta \langle L_0,L_1\rangle + \delta^2\langle L_0,L_2\rangle + \|\delta L_1+ \delta^2 L_2+\delta^3 L_3\|_F^2.

\end{equation}
Here the first term is responsible for the decrease in tensor loss:

\begin{align*}
\delta^3\langle L_0,L_3\rangle &= \delta^3\alpha\langle \point - \ten T,\bm a \otimes \bm b \otimes \bm c\rangle\\
&\leq \delta^3\alpha(K^2\sigma^2 - \ten T(\bm a,\bm b,\bm c))\\
&= -\delta^3\alpha\Omega(\kappa_2).
\end{align*}
For the other terms, we show that they are small enough so they will not cancel this improvement.

Observe that
\begin{align*}
\langle L_0,L_1\rangle &= \langle L_0, \Delta\ten S(\bm A, \bm B, \bm C)\rangle + \langle L_0, \ten S(\bm u\bm a^\top, \bm B, \bm C) + \ten S(\bm A, \bm v\bm b^\top, \bm C)\rangle\\
&= O(\alpha \sigma^2) + O(\kappa_1\sigma).
\end{align*}
The $O(\kappa_1\sigma)$ term appears because $\|\ten S_{2,1,1}(\bm A, \bm B, \bm C) - \ten T_{2,1,1}\|_F = O(\kappa_1)$,
$\|\ten S_{1,2,1}(\bm A, \bm B, \bm C) - \ten T_{1,2,1}\|_F = O(\kappa_1)$.

For the next term, we note that $\langle L_0, L_2\rangle$ is a sum of three inner products, any two of which we can make nonpositive by flipping the sign of $\Delta \ten S$ and one of $\Delta \bm A$, $\Delta \bm B$ (doing so doesn't change the amount by which the tensor loss decreases).
Hence, by design of Algorithm~\ref{alg:add_direction}, with constant probability we know that $\langle L_0,L_2\rangle \leq 0$.

As a result, we know \eqref{eq:loss_perturb} is at most $-\delta^3 \alpha \Omega(\kappa_2)$.

We now consider the perturbations of the regularizer.
Define the following terms:
\begin{align*}
\reg_{0,1} &= \bm A\bm A^\top - \ten S_{(1)}\ten S_{(1)}^\top,\quad \reg_{0,2} =\bm  B\bm B^\top - \ten S_{(2)}\ten S_{(2)}^\top,\quad \reg_{0,3} =\bm  C\bm C^\top - \ten S_{(3)}\ten S_{(3)}^\top\\
\reg_{1,1} &= \bm A\Delta\bm A^\top + \Delta\bm A\bm A^\top - \ten S_{(1)}(\Delta\ten S)_{(1)}^\top - (\Delta\ten S)_{(1)}\ten S_{(1)}^\top\\
\reg_{1,2} &= \bm B\Delta\bm B^\top + \Delta\bm B\bm B^\top - \ten S_{(2)}(\Delta\ten S)_{2)}^\top - (\Delta\ten S)_{(2)}\ten S_{(2)}^\top\\
\reg_{1,3} &= - \ten S_{(3)}(\Delta\ten S)_{(3)}^\top - (\Delta\ten S)_{(3)}\ten S_{(3)}^\top,\quad \reg_{2,3} = - (\Delta\ten S)_{(3)}(\Delta\ten S)_{(3)}^\top
\end{align*}
We bound these terms in norm as follows:
\begin{align*}
\|\reg_{1,1}\|_F &= \|\bm A\bm a\bm u^\top + \bm u\bm a^\top \bm A^\top - \bm u\ten S(\bm I,\bm v,\bm w)^\top - \ten S(\bm I,\bm v,\bm w)\bm u^\top\|_F\\
&\leq 2\|\bm A_2\|_F + 2\|\ten S(\bm I,\bm v,\bm w)\|_F\\
&\leq 2\sigma + 2\sqrt{\tau^{1/4}+\sigma^2}\\
&= O(\sigma).
\end{align*}
Likewise, $\|\reg_{1,2}\|_F = O(\sigma)$, $\|\reg_{1,3}\|_F = O(\sigma)$, and $\|\reg_{2,3}\| = O(1)$.
Also note that $\|\reg_{0,i}\|_F \leq \tau^{1/4}$ for $i=1,2,3$.
Using this,
we have
\begin{align*}
\|\reg_{0,1} + \delta \reg_{1,1}\|_F &\leq O(\tau^{1/4}) +O(\delta\sigma)\\
\|\reg_{0,2} + \delta \reg_{1,2}\|_F &\leq O(\tau^{1/4}) +O(\delta\sigma)\\
\|\reg_{0,3} +  \delta \reg_{1,3} + \delta^2 \reg_{2,3}\|_F &\leq O(\tau^{1/4}) + O(\delta\sigma) + O(\delta^2).
\end{align*}
All of these terms are dominated by $O(\delta^2)$, and so the perturbed regularizer is bounded by $O(\delta^8) = O(\sigma^2) = o(\sigma^{15/8})$. Hence, we see that the decrease in the tensor loss dominates the increase in the regularizer, as desired.
\end{proof}

We next address the case where $\ten T_{2,2,2}$ is large, which corresponds to $\bm A_1, \bm B_1, \bm C_1$ being rank deficient.
\begin{lemma}
\label{lem:add_3_directions}
Set  $\kappa_3 = 2K\sigma^{1/2}$.
Assume $R(\tup) < \tau$ and $\|\bm A_3\|_F$, $\|\bm B_3\|_F$, and $\|\bm C_3\|_F$ are all less than $\gamma$.
Further assume that $\|\ten T_{2,1,1}\|_2$, $\|\ten T_{1,2,1}\|_2$, and $\|\ten T_{1,1,2}\|_2$ and each less than $\kappa_1$,
while $\|\ten T_{2,2,1}\|_2$, $\|\ten T_{2,1,2}\|_2$, and $\|\ten T_{1,2,2}\|_2$ are each less than $\kappa_2$.
Let $\bm a, \bm b, \bm c, \bm u, \bm v, \bm w$ be the output of Algorithm \ref{alg:add_direction} with input $\bm A, \bm B, \bm C, \sigma, (2,2,2)$.
Define the directions $\Delta \bm A = \bm u \bm a^\top$, $\Delta \bm B = \bm v \bm b^\top$, $\Delta \bm C = \bm w \bm c^\top$, $\Delta \ten S = \bm u \otimes \bm v \otimes \bm w$.
If $\|\ten T_{2,2,2}\|_2 \geq \kappa_3$, then with constant probability, a step in these directions decreases the objective function
by $\Omega^*(\sigma^{3/4})$.
\end{lemma}
\begin{proof}
First observe that $\kappa_3 \geq 2K\sqrt{\gamma}$, which by Lemma \ref{lem:rank_bound} means that  $\text{rank}(\bm A_1)$, $\text{rank}(\bm B_1)$, and $\text{rank}(\bm C_1)$ are all strictly less than $r$.
Then  $\bm A_1$, $\bm B_1$, and $\bm C_1$ are all missing directions from the relevant subspaces of $\ten T$,
and we are near a fourth-order saddle point.
\begin{comment}
Let $\bm a', \bm b', \bm c'$ be sampled from the standard multivariate Guassian distribution on $U'_{1,2}$, $U'_{2,2}$, and $U'_{3,2}$, respectively.
Let $\bm u, \bm v, \bm w$ be unit vectors satisfying $\bm A_1^\top \bm u = \bm B_1^\top\bm v=\bm C_1^\top \bm w=0$.
\end{comment}
By lemma \ref{lem:anti}, with constant probability, $|\ten T(\bm a,\bm b,\bm c)| > C\kappa_3$ for some positive constant $C$.

Again  let $p(\delta) = f(\ten S+\delta \Delta \ten S, \bm A+\delta \Delta \bm A, \bm B+\delta\Delta \bm B, \bm C+\delta\Delta \bm C)$,
and set $\delta = \sigma^{1/8}$.
As in the proof of lemma \ref{lem:add_2_directions}, let for $i=0,\ldots,4$, let $L_i$ denote the $i$-th order perturbation term in
\[
(\ten S + \Delta \ten S)(\bm A + \Delta \bm A, \bm B + \Delta \bm B, \bm C + \Delta \bm C) - \ten T.
\]
We can upper bound each of these terms in norm, e.g.
\begin{align*}
\|L_1\|_F &= \|\bm A^\top \bm u \otimes \bm B^\top \bm v \otimes \bm C^\top \bm w + \ten S(\bm u\bm a^\top,\bm B,\bm C) + \ten S(\bm A,\bm v\bm b^\top,\bm C)\\
& + \ten S(\bm A,\bm B,\bm w\bm c^\top)\|_F\\
&\leq 8\sigma^3 + K^2(\|\ten S(\bm u,\bm I,\bm I)\|_F + \|\ten S(\bm I,\bm v,\bm I)\|_F+\|\ten S(\bm I,\bm I,\bm w)\|_F)\\
&\leq 8\sigma^3 + 3K^2\sqrt{\tau^{1/4}+2\sigma^2}\\
&= O(\sigma).
\end{align*}
Through similar calculations, we have $\|L_2\| = O(\sigma)$ and $\|L_3\| = O(\sigma)$.
On the other hand, $\|L_4\| \leq 1$ and $\|L_0\|\leq 2K$.
The perturbation in the tensor loss is then
\begin{equation}
\label{eq:loss_perturb2}
\sum_{i,j = 0}^4 \langle L_i,L_j\rangle \delta^{i+j}
\end{equation}
The decrease in the tensor loss is due to the following term:
\begin{align*}
\delta^4\langle L_0,L_4\rangle &= \delta^4\langle \point - \ten T,\bm a \otimes \bm b \otimes \bm c\rangle\\
&\leq \delta^4( K\sigma^3 - \ten T(\bm a,\bm b,\bm c))\\
&= -\delta^4\Omega(\kappa_3)\\
&= -\Omega(\sigma^{3/4}).
\end{align*}
By a simple Cauchy-Schwarz bound, the other perturbation terms in (\ref{eq:loss_perturb2})
are all bounded by $O(\sigma+ \delta^8) = O(\sigma) = o(\sigma^{3/4})$.

Now we analyze the perturbations of the regularizer.
As before, define the terms
\begin{align*}
\reg_{0,1} &= \bm A\bm A^\top - \ten S_{(1)}\ten S_{(1)}^\top,\quad \reg_{0,2} =\bm  B\bm B^\top - \ten S_{(2)}\ten S_{(2)}^\top,\quad \reg_{0,3} =\bm  C\bm C^\top - \ten S_{(3)}\ten S_{(3)}^\top\\
\reg_{1,1} &= \bm A\Delta\bm A^\top + \Delta\bm A\bm A^\top - \ten S_{(1)}(\Delta\ten S)_{(1)}^\top - (\Delta\ten S)_{(1)}\ten S_{(1)}^\top\\
\reg_{1,2} &= \bm B\Delta\bm B^\top + \Delta\bm B\bm B^\top - \ten S_{(2)}(\Delta\ten S)_{2)}^\top - (\Delta\ten S)_{(2)}\ten S_{(2)}^\top\\
\reg_{1,3} &= \bm C\Delta\bm C^\top + \Delta\bm C\bm C^\top - \ten S_{(3)}(\Delta\ten S)_{(3)}^\top - (\Delta\ten S)_{(3)}\ten S_{(3)}^\top
\end{align*}
We bound these terms in norm as follows:
\begin{align*}
\|\reg_{1,1}\|_F &= \|\bm A\bm a\bm u^\top + \bm u\bm a^\top \bm A^\top - \bm u\ten S(\bm I,\bm v,\bm w)^\top - \ten S(\bm I,\bm v,\bm w)\bm u^\top\|_F\\
&\leq 2\|\bm A_2\|_F + 2\|\ten S(\bm I,\bm v,\bm w)\|_F\\
&\leq 2\sigma + 2\sqrt{\tau^{1/4}+\sigma^2}\\
&= O(\sigma).
\end{align*}
Likewise, $\|\reg_{1,i}\|_F = O(\sigma)$ for $i=2,3$, and of course $\|\reg_{0,i}\|_F \leq \tau^{1/4}$ for $i=1,2,3$.
Again,
\begin{align*}
\|\reg_{0,i} + \delta \reg_{1,i}\|_F \leq O(\tau^{1/4}) + O(\delta\sigma)
\end{align*}
and using this, we can bound the perturbed regularizer as $O(\delta^4\sigma^4) = o(\sigma^{3/4})$.
Hence, the decrease in the tensor loss dominates all other perturbations, and we improve the objective function by $\Omega(\sigma^{3/4})$.
\end{proof}

config: arxiv