# Operational Quantum Mereology and Minimal Scrambling

Paolo Zanardi<EMAIL_ADDRESS>Department of Physics and Astronomy, Department
of Mathematics and Center for Quantum Information Science and Technology,
University of Southern California, Los Angeles, California 90089-0484, USA
Seth Lloyd<EMAIL_ADDRESS>MIT Department of Mechanical Engineering, 77
Massachusetts Avenue, Cambridge, MA 02139, USA  Turing Inc., Cambridge, MA
02139, USA

(August 28, 2024)

###### Abstract

In this paper we will attempt to answer the following question: what are the
natural quantum subsystems which emerge out a system’s dynamical laws? To
answer this question we first define generalized tensor product structures
(gTPS) in terms of observables, as dual pairs of an operator subalgebra $\cal
A$ and its commutant. Second, we propose an operational criterion of minimal
information scrambling at short time scales to dynamically select gTPS. In
this way the emergent subsystems are those which maintain the longest
“informational identity." This strategy is made quantitative by defining a
Gaussian scrambling rate in terms of the short-time expansion of an algebraic
version of the Out of Time Order Correlation (OTOC) function i.e., the $\cal
A$-OTOC. The Gaussian scrambling rate is computed analytically for physically
important cases of general division into subsystems, and is shown to have an
intuitive and compelling physical interpretation in terms of minimizing the
interaction strength between subsystems, and maximizing the effectiveness of
error-correcting codes.

##  I Introduction

Mereology is the theory of parthood relations – the relations of part to whole
and the relations of part to part within a whole. In this paper we try take
some steps towards an information-theoretic and operational framework for
quantum mereology Carroll and Singh (2021).

The first fundamental ingredient of this paper is provided by an extension the
algebraic approach to quantum virtual quantum subsystems (VQS) originally
advocated in Zanardi (2001a); Zanardi  _et al._ (2004).There the fundamental
idea is that operational constraints may limit the set of physically relevant
observables and operations to a subalgebra $\cal A$ of operators, which in
turn induces a decomposition of the state space into a direct sum of virtual
quantum subsystems. This generalized tensor product structure (gTPS) play a
key role in the theory of decoherence-free subspaces Zanardi and Rasetti
(1997); Lidar  _et al._ (1998), noiseless subsystems Knill  _et al._ (2000);
Zanardi (2000), quantum reference frames Bartlett  _et al._ (2007),
topological protection Zanardi and Lloyd (2003) and operator error correction
David Kribs and Poulin (2005). Some interesting recent developments of the
general theory can be found Kabernik (2018); Kabernik  _et al._ (2020).

It is of paramount importance to stress that such algebra-based strategy can
be applied to a variety situations in which there is no an _a priori_ locality
structure which gives a natural way of defining subsystems e.g., see Carroll
and Singh (2021) in the context of quantum gravity and, through operator error
correction, holography e.g., Harlow (2019); Chris Akers (2019). Also, this
approach is very close in spirit to the algebraic approach to quantum field
theory (QFT) see e.g., the classic Haag’s book Haag (1996) and the recent
Witten (2018) on entanglement in QFT. However, in this paper we will be
focusing on finite-dimensional Hilbert spaces which are more relevant to most
of quantum information.

The second fundamental ingredient is provided by the algebraic out of time
order commutator,“$\cal A$-OTOC," approach to quantum information scrambling
introduced in Zanardi (2021); Faidon Andreadakis (2022) for closed and open
quantum systems. The $\cal A$-OTOC formalism allows one to understand two
ostensibly unrelated physical problems, operator entanglement Zanardi (2001b)
Yan  _et al._ (2019); Styliaris  _et al._ (2021) and coherence-generating
power (CGP) Zanardi  _et al._ (2017a, b), from a single theoretical vantage
point.

The main goal of this paper is to blend synergistically the first two
ingredients. We will use an operational criterion of minimal scrambling at
short time scales to dynamically select generalized tensor product structures.
This strategy is intuitive as it amounts to say that the emergent subsystems
are those which maintain the longest an “informational identity". Given the
entropic nature of our scrambling measures this approach is akin to, and in
fact inspired by, the celebrated minimum entropy production principle Jaynes
(1980).

While not directly involving any quantum states, but just algebras of
observables, our strategy bears some resemblance with the so-called
“predictability sieve" Zurek (1993) for the emergence of classicality in
systems coupled with an environment. In Zurek (1993), Zurek showed how semi-
classical pointer variables emerge from the interaction between a system and
its environment: the pointer variables are those whose time evolution is most
predictable given the system dynamics. In Zurek’s work, the division into
system and environment is assumed to be given. In Carroll and Singh (2021),
Carroll and Singh extend Zurek’s criterion to identify the division into
system and environment that gives the maximally predictable pointer variables.
Our work extends the pointer variable approach to identify the division into
generalized subsystems that gives the maximal predictability/minimum
scrambling over the entire algebra of observables that defines a subsystem.

The paper is structured as follows. Sect (II) contains some introductory
material on notation and algebras. Sect. (III) discusses the gTPS concept used
in this paper. Sect. (IV) reviews definitions and basic results on the $\cal
A$-OTOC formalism for scrambling of algebras. In this section, we introduce
three physical examples, which we subsequently follow throughout the paper:
the first example is the scrambling rate of a subsystem; the second is the
coherence generating power of quantum dynamics; the third is the example of
quantum error correcting codes, which by definition suppress scrambling within
the code space. In Sect (V) the notion of Gaussian scrambling rate is
introduced and deployed to define dynamical emergence of gTPS for these
examples. In the first example, we provide a proof for the intuitive result
that the division into subsystems that minimizes subsystem scrambling is the
division that minimizes the norm of the interaction Hamiltonian. For case 2,
we bound the Gaussian scrambling rate by the coherence generating power of
maximal commuting subalgebras. For case 3, we relate scrambling rate to the
detection and correction of errors in a stabilizer code. Finally, Sect. (VI)
contains conclusions and outlook. The mathematical proofs of most of the
results are in the Appendix.

##  II Preliminaries

Let ${\cal H}$ be a $d$-dimensional Hilbert space and $L({\cal H})$ its the
full operator algebra. $L({\cal H})$ has a Hilbert space structure via the
Hilbert-Schmidt scalar product: $\langle
X,\,Y\rangle:=\mathrm{Tr}\left(X^{\dagger}Y\right)$ and norm
$\|X\|_{2}^{2}:=\langle X,\,X\rangle.$ This equips the space of superoperators
i.e., $L(L({\cal H}))$ with the scalar product $\langle{\cal T},\,{\cal
F}\rangle:=\mathrm{Tr}_{HS}\left({\cal T}^{\dagger}{\cal
F}\right)=\sum_{l,m}\langle m|{\cal T}^{\dagger}{\cal F}(|m\rangle\langle
l|)|l\rangle,$ and the norm

$\|{\cal T}\|_{HS}^{2}=\langle{\cal T},\,{\cal T}\rangle=\sum_{l,m}\|{\cal
T}(|m\rangle\langle l|)\|_{2}^{2}.$

For example, If ${\cal T}(X)=\sum_{i}A_{i}XA_{i}^{\dagger},$ then $\|{\cal
T}\|_{HS}^{2}=\sum_{i,j}|\mathrm{Tr}(A_{i}^{\dagger}A_{j})|^{2}.$ Moreover, if
$\mathbb{P}$ is an orthogonal projection, its rank is given by
$\|\mathbb{P}\|_{HS}^{2}=\mathrm{Tr}_{HS}\mathbb{P}.$

The key objects of this paper are _hermitian-closed unital subalgebras_ ${\cal
A}\subset L({\cal H})$ and their commutants

$\displaystyle{\cal A}^{\prime}:=\\{X\in L({\cal
H})\,|\,[X,\,Y]=0,\,\forall\,Y\in{\cal A}\\}.$ (1)

and centers ${\cal Z}({\cal A}):={\cal A}\cap{\cal A}^{\prime}.$

For these algebras the double commutant theorem holds: $({\cal
A}^{\prime})^{\prime}={\cal A}.$ If $\cal A$ (${\cal A}^{\prime}$) is abelian
one has that ${\cal A}\subset{\cal A}^{\prime}$ (${\cal
A}^{\prime}\subset{\cal A}$) and therefore ${\cal Z}({\cal A})={\cal A}$
(${\cal Z}({\cal A})={\cal A}^{\prime}$).

The fundamental structure theorem of these objects states that the Hilbert
space breaks into a direct sum of $d_{Z}:=\mathrm{dim}\,{\cal Z}({\cal A})$
blocks and each of them has a tensor product bipartite structure

$\displaystyle{\cal H}=\bigoplus_{J=1}^{d_{Z}}{\cal H}_{J},\qquad{\cal
H}_{J}\cong\mathbf{C}^{n_{J}}\otimes\mathbf{C}^{d_{J}}.$ (2)

The factors $\mathbf{C}^{n_{J}}$ and $\mathbf{C}^{d_{J}}$ are VQS Zanardi
(2001a). Moreover, at the algebra level one has that $\cal A$ (${\cal
A}^{\prime}$) acts irreducibly on the $\mathbf{C}^{d_{J}}$ factors
($\mathbf{C}^{n_{J}}$) ${\cal
A}\cong\bigoplus_{J=1}^{d_{Z}}\mathbf{1}_{n_{J}}\otimes
L(\mathbf{C}^{d_{J}}),\quad{\cal
A}^{\prime}\cong\bigoplus_{J=1}^{d_{Z}}L(\mathbf{C}^{n_{J}})\otimes\mathbf{1}_{d_{J}}.$Whence,
$d=\sum_{J}n_{J}d_{J},$ and

$\mathrm{dim}\,{\cal A}=\sum_{J}d_{J}^{2}=:d({\cal
A}),\quad\mathrm{dim}\,{\cal A}^{\prime}=\sum_{J}n_{J}^{2}=:d({\cal
A}^{\prime}).$

If $\cal A$ (${\cal A}^{\prime}$) is abelian then $d_{J}=1,\,(\forall J)$
($n_{J}=1,\,(\forall J)$). By defining the $d_{Z}$-dimensional (integer-
valued) vectors ${\bf{d}}:=(d_{J})_{J}$, and ${\bf{n}}:=(n_{J})_{J}$ one sees
that

$d^{2}=(\mathbf{n}\cdot\mathbf{d})^{2}\leq\|\mathbf{n}\|^{2}\|\mathbf{d}\|^{2}=d({\cal
A})d({\cal A}^{\prime}).$

If ${\bf{d}}=\lambda{\bf{n}}$ one has that the above inequality becomes an
equality i.e., $d^{2}=d({\cal A})d({\cal A}^{\prime}),$ In this case the pair
$({\cal A},\,{\cal A}^{\prime})$ will be referred to as _collinear_. The
center of $\cal A$ is spanned by the projections over the central blocks

${\cal Z}({\cal
A})=\bigoplus_{J=1}^{d_{Z}}\mathbf{C}\\{\Pi_{J}:=\mathbf{1}_{n_{J}}\otimes\mathbf{1}_{d_{J}}\\}.$

Associated to any algebra $\cal A$ we have an orthogonal projection Completely
Positive (CP) map: $\mathbb{P}_{\cal A}^{\dagger}=\mathbb{P}_{\cal
A},\,\mathbb{P}_{\cal A}^{2}=\mathbb{P}_{\cal A}$ and
$\mathrm{Im}\,\mathbb{P}_{\cal A}={\cal A}$ 111 In terms of (2) one has
$\mathbb{P}_{{\cal
A}}(X)=\sum^{\oplus}_{J}\frac{\mathbf{1}_{n_{J}}}{n_{J}}\otimes\mathrm{tr}_{n_{J}}(X),$
and $\mathbb{P}_{{\cal
A}^{\prime}}(X)=\sum^{\oplus}_{J}\mathrm{tr}_{d_{J}}(X)\otimes\frac{\mathbf{1}_{d_{J}}}{d_{J}}.$.
Using these projections one can define a distance between two algebras $\cal
A$ and $\cal B$:

$\displaystyle D({\cal A},\,{\cal B}):=\|\mathbb{P}_{\cal A}-\mathbb{P}_{\cal
B}\|_{HS}.$ (3)

If $U$ is a unitary we denote by ${\cal U}(X):=UXU^{\dagger}$ and ${\cal
U}({\cal A}):=\\{{\cal U}(a)\,|\,a\in{\cal A}\\}$ is the image algebra. The
associated projection is given by $\mathbb{P}_{{\cal U}({\cal A})}={\cal
U}\mathbb{P}_{{\cal A}}{\cal U}^{\dagger}.$

##  III Generalized TPS

At the formal level, the standard “tensor product axiom" of quantum theory
says that if we consider the system obtained by the union of two systems $A$
and $B$ then the associated Hilbert Space ${\cal H}$ is given by the tensor
product of the Hilbert spaces associate with the individual subsystems i.e.,
${\cal H}\cong{\cal H}_{A}\otimes{\cal H}_{B}.$ At the level of observables
one postulates $L({\cal H})\cong L({\cal H}_{A})\otimes L({\cal H}_{B}),$
namely the full-operator algebra is the tensor product of the subsystems
operator algebras. By denoting with ${\cal A}:=L({\cal
H}_{A})\otimes{\mathbf{1}}_{B},$ and ${\cal
A}^{\prime}:={\mathbf{1}}_{A}\otimes L({\cal H}_{B})$ one can write

$\displaystyle{\cal A}\otimes{\cal A}^{\prime}\cong{\cal A}\vee{\cal
A}^{\prime}\cong L({\cal H})$ (4)

where the ${\cal A}\vee{\cal A}^{\prime}$ denotes the algebra generated by the
subalgebras $\cal A$ and ${\cal A}^{\prime}$ i.e., ${\cal A}\vee{\cal
A}^{\prime}:=\\{\sum_{i}a_{i}b_{i}\,|\,a_{i}\in{\cal A},\,b_{i}\in{\cal
A}^{\prime}\\}.$ Now, if ${\cal A}$ is any (hermitian-closed, unital)
subalgebra of $L({\cal H})$ and (4) is fulfilled, we say that the dual pair
$({\cal A},\,{\cal A}^{\prime})$ defines a virtual bipartition or a Tensor
Product Structure (TPS) Zanardi (2001a).

The latter are by no-means unique e.g., every unitary mapping $U$ over $\cal
H$ gives rise to a dual pair $({\cal A}_{U}\,{\cal A}_{U}^{\prime})$ (${\cal
A}_{U}:={\cal U}({\cal A})$) which satisfies (4), which one of these TPSs is
the “real" or “physical one" depends, again, on the operationally available
resources . It is important to emphasize that this is true even when one knows
that ${\cal H}={\cal H}_{A}\otimes{\cal H}_{B}$ as the local algebras might
not be implementable. If one has control only on $\cal A$ then the associated
physical degrees of freedom can be seen as the “system" whereas those
supported by ${\cal A}^{\prime}$ can be seen as the “environment" (and
viceversa). Also, ${\cal A}^{\prime}$ comprises the “symmetries" of $\cal A$
(and viceversa).

In this paper we will consider an even more general situation. Suppose that
operational constraints on physical resources leads to the selection of
specific class of realizable operators (observables and operations) forming an
algebra $\cal A$ which does not fulfill (4) but just

$\displaystyle{\cal A}\vee{\cal A}^{\prime}\subset L({\cal H}).$ (5)

In this case we say that the dual pair $({\cal A},\,{\cal A}^{\prime})$
defines a generalized TPS (gTPS). While (5) is always satisfied, in order to
meet the standard condition (4) one must have that $\cal A$ is a factor i.e.,
the center ${\cal Z}({\cal A})$ contains just scalars or, equivalently, there
is just one $J$ in the decomposition (2)App . On the other hand, when
$A^{\prime}$ is abelian one has that $n_{J}=1,\,(\forall J)$ and the
decomposition (2) is a form of superselection with the elements of ${\cal
Z}({\cal A})={\cal A}^{\prime}$ playing the role of “superselection charges".

We would like to stress that we regard both the tensor and the additive
structure in Eq. (2) as elements of quantum mereology which in this way
conceptually unifies these two aspects. The first one, is the partition into
subsystems while the second describes the partition of the state-space into
central symmetry sectors. The latter are labelled by the the super-selection
charges joint eigenvalues and are dynamically decoupled insofar the operations
belong to ${\cal A}$ 222For a CP map this means that the associated Krauss
operators are in $\cal A$..

###  III.1 Noiseless Subsystems for collective decoherence

To illustrate these concepts let us consider symmetry-protected quantum
information Zanardi (2000). In this case Eq. (4) is not satisfied as the
relevant algebra is not a factor and therefore the state-space splits into
disjoint symmetry sectors.. Let us consider a system comprising $N$ physical
qubits in which the only allowed operations e.g., for the lack of spatial
resolution, are global . The algebra $\cal A$ is here given by the operators
invariant under qubit permutations. It turns out that this is the unital
algebra is generated by the collective spin operators
$S^{\alpha}:=\sum_{j=1}^{N}\sigma^{\alpha}_{j},\,(\alpha=x,y,z)$ and that the
Hilbert ${\cal H}=(\mathbf{C}^{2})^{\otimes N}$ breaks down into
$d_{J}=2J+1$-dimensional irreducible components, each with a multiplicity
$n_{J},$ labelled by the total angular momentum $J$: ${\cal H}=\oplus_{J}{\cal
H}_{J}.$ For any given value of the quantum number $J$ one has virtual
bipartition ${\cal H}_{J}\cong\mathbf{C}^{n_{J}}\otimes\mathbf{C}^{d_{J}}.$ In
the context of decoherence protection $\cal A$ is the “interaction" algebra
generated by the system’s operators coupled to the environment and one has
that the the $\mathbf{C}^{n_{J}}$’s are acted trivially by $\cal A$ and
therefore provide “virtual noiseless subsystems" where information can be
encoded and safely stored Knill  _et al._ (2000). These noiseless subsystems
can be then (universally) acted upon by elements of the commutant ${\cal
A}^{\prime},$ the latter given by the group algebra of permutations generated
by pair-wise Heisenberg interactions. The center ${\cal Z}({\cal A})$ is just
the abelian algebra generated by the total angular momentum operator
$S^{2}:=\sum_{\alpha=x,yz}(S^{\alpha})^{2}.$

##  IV Scrambling of Algebras.

We can now introduce the central object of our algebraic approach to quantum
scrambling: the $\mathbf{\cal A}$-OTOC. This tool was introduced in Zanardi
(2021) for closed systems and extended to open ones in Faidon Andreadakis
(2022). It is defined as

$\displaystyle{G}_{{\cal A}}({\cal U}):=\frac{1}{2d}\,\mathbb{E}_{X\in{\cal
A},\,Y\in{\cal A}^{\prime}}\left[\|[X,\,{\cal U}(Y)]\|_{2}^{2}\right].$ (6)

where ${\cal U}(X):=U^{\dagger}XU$ ($U$ unitary over $\cal H$). Here
$\mathbb{E}$ denotes the Haar-average over the unitaries $X$ ($Y$) in $\cal A$
(${\cal A}^{\prime}$).Roughly, the $\cal A$-OTOC measures how much the
symmetries of the VQS associated to $\cal A$ are dynamically broken by ${\cal
U}.$ From Eq. (6) it follows immediately that ${G}_{{\cal A}}({\cal
U})={G}_{{\cal A}^{\prime}}({\cal U}^{\dagger}),$ moreover in the collinear
case one has ${G}_{{\cal A}}={G}_{{\cal A}^{\prime}}$ and therefore
${G}_{{\cal A}}({\cal U})=G_{{\cal A}}({\cal U}^{\dagger})$.

In the collinear case the $\cal A$-OTOC has simple geometrical interpretation
in terms of the distance between algebras defined in Eq. (3) Zanardi (2021)

$\displaystyle{G}_{{\cal A}}({\cal U})=\frac{1}{2}\frac{D^{2}({\cal
A}^{\prime},{\cal U}({\cal A}^{\prime}))}{d({\cal A}^{\prime})}.$ (7)

Namely, the $\cal A$-OTOC quantifies how far the commutant is mapped from
itself by the dynamics . Clearly, this distance is maximal i.e., maximal
scrambling, when ${\cal A}^{\prime}$ gets othogonalized to itself by the
action of $\cal U$.

We will now consider three important physically motivated examples, all of
them collinear, in which the $\cal A$-OTOC can be fully computed analytically
(more details about the first two cases can be found in Zanardi (2021)).

1) Let us consider a bipartite quantum system with ${\cal H}={\cal
H}_{A}\otimes{\cal H}_{B}$ and ${\cal A}=L({\cal H}_{A})\otimes\mathbf{1}_{B}$
and, therefore, ${\cal A}^{\prime}=\mathbf{1}_{A}\otimes L({\cal H}_{B}).$ In
this case one gets back to the averaged bipartite OTOC discussed in Styliaris
_et al._ (2021).

$\displaystyle G_{\cal A}({\cal U})=1-\frac{1}{d^{2}}\langle
S_{AA^{\prime}},\,{\cal U}^{\otimes\,2}(S_{AA^{\prime}})\rangle,$ (8)

where $d=d_{A}d_{B}=\mathrm{dim}\,{\cal H}\,,(d_{X}=\mathrm{dim}\,{\cal
H}_{X}\,(X=A,B))$ and $S_{AA^{\prime}}$ is the swap between the $A$ factors in
${\cal H}^{\otimes\,2}$ This a remarkable formula, as it allows one to
_rigorously_ prove a wealth of results and unveil several relations between
$G_{\cal A}(U)$ and other physical quantities.

2) Let ${\cal A}_{B}={\cal A}_{B}^{\prime}$ be the algebra of operators which
are diagonal with respect to an orthonormal basis
$B:=\\{|i\rangle\\}_{i=1}^{d}$ i.e., ${\cal
A}_{B}=\mathbf{C}\,\\{\Pi_{i}:=|i\rangle\langle i|\\}_{i=1}^{d}.$ This is a
$d$-dimensional maximal abelian subalgebra.

$\displaystyle G_{{\cal A}_{B}}({\cal
U})=1-\frac{1}{d}\sum_{i,j=1}^{d}|\langle i|U|j\rangle|^{4}.$ (9)

This expression coincides with the _coherence-generating power_ (CGP) of $U$
introduced in Zanardi  _et al._ (2017a); Styliaris  _et al._ (2019). CGP is
there defined as the average coherence (measured by the the sum of the square
of off-diagonal elements, with respect $B$) generated by $U$ starting from any
of the pure incoherent states $\Pi.$ Geometrically the CGP is proportional to
the distance $D({\cal A}_{B},{\cal U}({\cal A}_{B}))$ Zanardi and Campos
Venuti (2018) and has been applied to the detection of the localization
transitions in many-body systems Styliaris  _et al._ (2019), and to detection
of quantum chaos in closed and open systems Anand  _et al._ (2021).

3) Let $\\{S_{l}\\}_{l=1}^{n-k}$ be a set of stabilizer operators over
$n$-qubits Gottesman (1997),
$G_{S}=\\{\prod_{l=1}^{n-k}S_{l}^{\alpha_{l}}\,|\,(\alpha_{l})_{l}\in\\{0,1\\}^{n-k}\\},$
the stabilizer group they generate and ${\cal A}:=\mathbf{C}[G_{S}]$ its group
algebra. In Eq. (2) now we have
$J=(j_{l})_{l}\in\\{-1,\,1\\}^{n-k},\,n_{J}=2^{k},\,d_{J}=1.$ The VQS
$\mathbf{C}^{n_{J}}$ with $J=(1,\ldots,1)$ (identity irrep of $G_{S}$ and
$\cal A$) is a quantum error correcting code Gottesman (1997). The $\cal
A$-OTOC:

$\displaystyle G_{{\cal A}_{S}}({\cal U})=1-\frac{1}{2^{3n-k}}\sum_{g,h\in
G_{S}}|\langle g,{\cal U}(h)\rangle|^{2}.$ (10)

###  IV.1 Mereological Entropies

It is important to stress that $1-G_{\cal A}({\cal U})$ can be regarded as a
generalized purity Barnum  _et al._ (2004) and that the $\cal A$-OTOC itself
is therefore a type of generalized linear entropy.

For example, in the bipartite case 1) the $\cal A$-OTOC is identical to the
operator linear entanglement entropy of $U$ as well as to the average linear
entropy production of the channel $T(\rho):=\mathrm{Tr}_{B}\left[{\cal
U}(\rho\otimes\frac{\mathbf{1}}{d_{B}})\right]$ over pure $\rho$’s Styliaris
_et al._ (2021). This is an entropic contribution purely at the level of the
multiplicative mereological structure.

On the other hand, for abelian ${\cal A}^{\prime}={\cal Z}({\cal A})$ the
$\cal A$-OTOC is an average of the linear entropies of the probability vectors
$\mathbf{p}_{J}:=\frac{1}{d_{J}}(\langle{\Pi_{J}},{\cal
U}(\Pi_{K})\rangle)_{K=1}^{d_{Z}}$

$\displaystyle G_{\cal A}({\cal U})=\sum_{J}q_{J}S_{L}(\mathbf{p}_{J}),\quad
q_{J}:={d_{J}}/{d},$ (11)

where $S_{L}(\mathbf{p}_{J}):=1-\|\mathbf{p}_{J}\|^{2},$ and
$J=1,\ldots,d_{Z}.$ Since, from Eq. (6), one immediately sees that $G_{\cal
A}({\cal U})=G_{{\cal A}^{\prime}}({\cal U}^{\dagger})$ for abelian $\cal A$
we have the same result with with $n_{J}$ and ${\cal U}^{\dagger}$ in lieu of
$d_{J}$ and $\cal U$ respectively. These entropies measure how uniformly the
$\Pi_{K}$’s are spread across the system of central sectors by the action of
$U.$ This is an entropic contribution purely at the level of the additive
mereological structure.

For general $\cal A$ both the additive and the multiplicative mereological
structures contribute to the $A$-OTOC entropy. One has contributions from the
“uniformization" of the the central sector system (due to the the "off-
diagonal" $U_{JK}:=\Pi_{J}U\Pi_{K}:$ for $J\neq K$) and the operator
entanglement of the individual $U_{JK}$ App .

##  V Scrambling and subsystem emergence

We will now show how the $\cal A$-OTOC formalism developed so far can be used
to define dynamical emergence of subsystems. Qualitatively, the idea is, given
a Hamiltonian $H$ and an algebra $\cal A$, to define a notion of “scrambling
time" (“scrambling rate") $\tau_{s}(H,{\cal A})$ ($\tau_{s}^{-1}(H,{\cal A})$)
which is the time scales needed to have non-trivial scrambling i..e, if
$t\ll\tau_{s}$ no scrambling occurs. Once this is done one can select algebras
(i.e., gTPS) by maximizing (minimizing) $\tau_{s}$ ($\tau^{-1}$) over a family
$\mathbb{A}$ of operationally available $\cal A$’s. Symbolically

$\displaystyle\\{\textit{Emergent}\,{\cal A}\\}:=\mathrm{argmin}_{{\cal
A}\in\mathbb{A}}\,\tau_{s}^{-1}(H,{\cal A})$ (12)

Quantitatively, the starting point of our investigations is the following
result on the short-time dynamics of the $\cal A$-OTOC for Hamiltonian systems
$U_{t}=e^{-iHt}.$

PropositionApp  i) $G_{{\cal A}}({\cal U}_{t})=2(t/\tau_{s})^{2}+O(t^{3})$
where the “gaussian scrambling rate " $\tau_{s}^{-1}$ is given by

$\displaystyle\tau^{-1}_{s}(H,{\cal A})=\|(1-\mathbb{P}_{{\cal A}+{\cal
A}^{\prime}})\tilde{H}\|_{2}.$ (13)

where we defined the normalized Hamiltonian $\tilde{H}:=\frac{H}{\sqrt{d}}.$
The “gaussian scrambling time " $\tau_{s}$ can be regarded as defining the
period over which scrambling is negligible and information “locally" encoded
in $\cal A$ is retained

ii) $G_{{\cal A}}({\cal U}_{t})=0\,(\forall t)$ if (and only if) $H$ belongs
to the operator subspace ${\cal A}+{\cal A}^{\prime}:=\\{a+b\,|\,a\in{\cal
A},\,b\in{\cal A}^{\prime}\\}.$

iii) Using the standard Hilbert-space notion of the distance between a vector
$x$ and a subspace Eq. (13) can be recast into an even more geometrical
fashion:

$\displaystyle\tau^{-1}_{s}(H,{\cal A})=D(\tilde{H},\,{\cal A}+{\cal
A}^{\prime}).$ (14)

In words: for any ${\cal A}$ the gaussian scrambling rate is the distance
between the assigned (normalized) Hamiltonian and the sum of the operator
subspaces $\cal A$ and ${\cal A}^{\prime}.$ When such a distance vanishes then
the $\cal A$-OTOC is identically zero at all times.

iv) The following upper-bounds hold:

$\displaystyle\tau_{s}^{-1}(H,{\cal A})\leq\mathrm{min}\\{D(\tilde{H},{\cal
A}),\,D(\tilde{H},{\cal A}^{\prime})\\}\leq\eta_{H},$ (15)

where $\eta_{H}:=\|\tilde{H}\|_{2}$ is a natural energy scale associated with
$H$ (whose inverse sets the physical unit of time). The first bound above
implies the nearly obvious fact that if $H$ belong either to $\cal A$ or
${\cal A}^{\prime}$ then there is no scrambling. Also, if either $\cal A$ or
${\cal A}^{\prime}$ are abelian then the first upper-bound is saturated. On
the other hand, Hamiltonians orthogonal ${\cal A}+{\cal A}^{\prime}$ will
saturate the last upper-bound and correspond to the fast scramblers in this
short-time (gaussian) regime.

v) The rate is given by two different types of contributions: coupling between
different central sectors $\Pi_{J}{\cal
H}\cong\mathbf{C}^{n}_{J}\otimes\mathbf{C}^{d_{J}}$ in (2) and entangling
“interactions" within them. When either $\cal A$ or ${\cal A}^{\prime}$ is
Abelian the second contribution vanishes and one has
$\tau^{-1}_{s}=\|(1-\mathbb{P}_{{\cal A}\vee{\cal
A}^{\prime}})\tilde{H}\|_{2},$ or even more explicitly

$\displaystyle
1/\tau_{s}^{2}={\sum_{J}\|\Pi_{J}\tilde{H}(1-\Pi_{J})\|_{2}^{2}}.$ (16)

In the light of these results the minimization problem (12) has the following
neat (yet formal) geometrical solution: the dynamically “emergent" gTPS are
those associated to the ${\cal A}\in\mathbb{A}$ such that the operator vector
space ${\cal A}+{\cal A}^{\prime}$ has minimum distance from the Hamiltonian
$H.$ In particular, $\cal A$’s such that that distance is zero ($\eta_{H}$)
correspond to no scrambling (fast scramblers). Moreover, when $\cal A$ (${\cal
A}^{\prime}$) is abelian then ${\cal A}+{\cal A}^{\prime}$ in the above can be
replaced by ${\cal A}^{\prime}$ ($\cal A$).

###  V.1 Three Examples

Let us now consider again the cases 1)-3) in the above. We will show the
explicit form for $\tau_{S}(H,{\cal A})$ in these cases and that in these
important situations Eq. (13) has a very physically transparent
interpretation. This fact provides a key motivation to pursue the gaussian
scrambling rate formalism in this paper.

1’) Spatial Bipartitions: Here we consider a state-space which is given a
“fundamental" multipartition into $N$ (ordered) qubits ${\cal
H}=(\mathbf{C}^{2})^{\otimes\,N}.$ If $S\subset\\{1,\ldots,N\\}$ (and
$\bar{S}$ is its complement) then, with obvious notation, one has ${\cal
H}={\cal H}_{S}\otimes{\cal H}_{\bar{S}}$ and the local observables Algebras
${\cal A}_{S}:=L({\cal H}_{S})\otimes\mathbf{1}_{\bar{S}}$ and ${\cal
A}_{S}^{\prime}=\mathbf{1}_{S}\otimes L({\cal H}_{\bar{S}}).$ Since
$\mathbb{P}_{{\cal
A}_{S}}(X)=\mathrm{Tr}_{\bar{S}}X\otimes\frac{\mathbf{1}}{d_{\bar{S}}},\,,\mathbb{P}_{{\cal
A}_{\bar{S}}}(X)=\frac{\mathbf{1}}{d_{{S}}}\otimes\mathrm{Tr}_{{S}}X,$ and
$\mathbb{P}_{{\cal A}_{S}}\mathbb{P}_{{\cal
A}_{\bar{S}}}(X)=\frac{\mathrm{Tr}(X)}{d}\mathbf{1}$ Eq. (13) takes here the
form:

$\displaystyle
1/\tau_{s}=\|\tilde{H}-\frac{\mathbf{1}_{S}}{d_{S}}\otimes\mathrm{Tr}_{S}(\tilde{H})-\mathrm{Tr}_{\bar{S}}(\tilde{H})\otimes\frac{\mathbf{1}_{\bar{S}}}{d_{\bar{S}}}\|_{2},$
(17)

where, for simplicity, we assumed a traceless $H$ and
$d_{X}=2^{|X|},(X=S,\bar{S}).$ Here we see that the projection
$1-\mathbb{P}_{{\cal A}+{\cal A}^{\prime}}$ – namely the projection onto
$({\cal A}+{\cal A}^{\prime})^{\perp}$ – in Eq. (13) is nothing but the
extraction of the $S$-${\bar{S}}$-interaction part of $H.$ This result leads
to a particularly intuitive and satisfactory sense of “subsystems emergence
from minimal scrambling:" given a family $\mathbb{S}$ of subsets of
$\\{1,\ldots,N\\}$ the Hamiltonian $H$ will select those $S\in\mathbb{S}$ such
that $S$-${\bar{S}}$-interaction part of $H$ has minimal norm i.e., those
which are minimally coupled with the rest of the system.

2’) Maximal Abelian Algebras: If ${\cal
A}_{B}=\mathrm{span}\\{|j\rangle\langle j|\\}={\cal A}_{B}^{\prime},$ where
the $|j\rangle$’s form a basis $B,$ then, from Eq. (16), the gaussian
scrambling rate is the (Hilbert-Schmidt) norm of the off-diagonal (in the
basis $B$) part of $\tilde{H}.$ Intuitively, this quantity is as small as
possible when the eigenbasis $B_{H}$ of $H$ and $B$ are as close as possible:
the dynamically selected ${\cal A}_{B}$’s are the closest to the one generated
by $H.$ Indeed, If $H$ is non degenerate with an eigenbasis $B_{H},$ one can
prove the bound

$\displaystyle\tau^{-1}_{s}(H,{\cal A}_{B})\leq\eta_{H}\,D({\cal
A}_{B},\,{\cal A}_{B_{H}}).$ (18)

Here $D$ denotes the distance between algebras defined in the above and
studied, in relation to CGP, in Zanardi and Campos Venuti (2018).

3’) Stabilizer Algebra:Here one has that $\mathbb{P}_{{\cal
A}_{S}^{\prime}}(X)=|G_{S}|^{-1}\sum_{g\in G_{S}}gXg^{\dagger},$ from v) above
one finds

$\displaystyle\tau^{-1}_{s}(H,{\cal A}_{S})=\|(1-\mathbb{P}_{{\cal
A}_{S}^{\prime}})\tilde{H}\|_{2}.$ (19)

If $H$ anticommutes with any of the stabilizer generators $S_{l}$’s (see 3)
above) then $\mathbb{P}_{{\cal A}_{S}^{\prime}}(\tilde{H})=0$ and the
scrambling rate (19) is maximal. This is exactly the condition for $H$ to
generate (correctable) errors in the associate error correcting code. The
elements in ${\cal A}_{S}^{\prime}$ not in ${\cal A}_{S}$ correspond to non-
trivial operations on the code or to uncorrectable errors Gottesman (1997) and
have $\tau^{-1}_{s}=0$.

###  V.2 Rate minimization over families of algebras

In this section we are going to illustrate the minimization strategy (12) by
means of toy-models with “circular" families of algebras. In the first
(second) case we have a continuous family of bi-partitions (bases) of the two-
qubit (one-qubit) space. The third case corresponds to a family obtained by
single-qubit rotations of two-qubit symmetric operators.

At the formal level a general way to build a family of algebras is to consider
the adjoint orbit $\mathbb{A}:=\\{{\cal A}_{U}:={\cal U}({\cal
A})\\}_{U\in\mathbb{U}},$ of a given $\cal A,$ for $U$ ranging in some set
$\mathbb{U}$ of unitaries. Operationally, this means that the observer has the
ability to implement elements of $\cal A$ and the unitaries in $\mathbb{U}$.
From (14) it easily follows the covariance relation

$\displaystyle\tau_{s}(H,{\cal U}({\cal A}))=\tau_{s}({\cal
U}^{\dagger}(H),{\cal A}),$ (20)

which, in turn, shows that minimizing $\tau^{-1}_{s}(H,\bullet)$ over the
adjoint orbit of $\cal A$ is equivalent to minimize the scrambling rate of
$\cal A$ over an orbit of Hamiltonians $\mathbb{H}:=\\{{\cal
U}^{\dagger}(H)\\}_{U\in\mathbb{U}}$ i.e., minimizing
$\tau^{-1}_{s}(\bullet,{\cal A})\colon\mathbb{H}\rightarrow\mathbf{R}.$

1”) Consider ${\cal H}=\mathbf{C}^{2}\otimes\mathbf{C}^{2},$ with
$H=\sigma^{z}\otimes\mathbf{1}$ and the family ${\cal
A}_{\theta}:=U_{\theta}{\cal A}_{0}U_{\theta}^{\dagger},$ where ${\cal
A}_{0}=L(\mathbf{C}^{2})\otimes\mathbf{1},$ and
$U_{\theta}:=e^{i\frac{\theta}{2}\sigma^{x}\otimes\sigma^{x}}.$ From Eq. (17)
$\tau^{-1}_{s}(H,{\cal A}_{\theta})=|\sin\theta|.$ Non-trivial )vanishing rate
for $\theta=\pi$ ($U_{\pi}\neq\mathbf{1}$ but ${\cal A}_{0}={\cal A}_{\pi}$)
and gaussian fast scrambler for $\theta=\pi/2$ when the Hamiltonian is “pure"
interaction.

2”) Consider ${\cal H}=\mathbf{C}^{2}$ and $H=\sigma^{z}$ and the family
${\cal A}_{B_{\theta}}$ where
$B_{\theta}=\\{U_{\theta}|0\rangle,\,U_{\theta}|1\rangle\\},$ and
$U_{\theta}:=e^{i\frac{\theta}{2}\sigma^{y}}.$ From v) and (20) one finds
$\tau^{-1}_{s}(H,{\cal A}_{B_{\theta}})=|\sin\theta|.$ Non-trivial vanishing
rate for $\theta=\pi$ ($U_{\pi}\neq\mathbf{1}$ but ${\cal A}_{0}={\cal
A}_{\pi}$) and gaussian fast scrambler for $\theta=\pi/2$ when the $B_{\pi/2}$
is mutually unbiased with respect to $B_{0}$ (and the rotated algebra ${\cal
A}_{B_{\pi/2}}$has maximal distance from ${\cal A}_{B_{0}}$).

3”) Consider ${\cal H}=\mathbf{C}^{2}\otimes\mathbf{C}^{2},$ with
$H=\sigma^{z}\otimes\mathbf{1}+\mathbf{1}\otimes\sigma^{z}$ and the family
${\cal A}_{\theta}:=U_{\theta}{\cal A}_{0}U_{\theta}^{\dagger},$ where ${\cal
A}_{0}=\mathbf{C}\\{\mathbf{1},\,S\\}^{\prime}$ ($S$ swap operator) and
$U_{\theta}:=e^{i\frac{\theta}{2}\sigma^{y}}\otimes\mathbf{1}.$ From v) and
(20) one obtains $\tau^{-1}_{s}(H,{\cal
A}_{\theta})=\frac{1}{4}\|H_{\theta}-SH_{\theta}S\|_{2}=\sqrt{2}\sin(\theta/2),$
where $H_{\theta}:=U_{\theta}^{\dagger}HU_{\theta}.$ Here $\theta=\pi$ is a
gaussian fast scrambler as the rotated Hamiltonian $H_{\pi}$ is now anti-
symmetric and thus orthogonal to ${\cal A}_{0}.$

While in these cases the optimization problem for $\tau_{s}^{-1}$ is, by
construction, straightforward, in general it might be a quite challenging one,
even in physically intuitive cases. To better appreciate this fact let us now
go back to the Spatial Bipartitions case above and suppose that one is given a
$N$-qubit space ${\cal H}=(\mathbf{C}^{2})^{\otimes\,N}$ and a graph ${\cal
G}:=(V,E)$ with $N$-vertices ($N=|V|$) and a Ising interaction for each edge:
$\tilde{H}=2^{-N/2}\sum_{(i,j)\in E}H_{ij}.$ For any (non-trivial) subset of
vertices $S\subset V$ the corresponding rate can be readily obtained from Eq.
(17):

$\displaystyle\tau_{s}^{-1}(H,{\cal A}_{S})=\sum_{(i,j)\in\partial
S}J_{ij}^{2},$ (21)

where $\partial S:=\\{(i,j)\in E\,|\,i\in S\,\mathrm{and}\,j\in\bar{S}\\}.$
The minimization of this quantity over all $S$’s is a problem which depend
both on the graph topology and on the actual value of the coupling constants
$J_{ij}.$ This the well-known problem min-cut in Graph Theory whose complexity
depends of the $J_{ij}^{\prime}s.$ In particular, if the latter are edge
independent, say $J_{ij}=1,$ one finds $\tau_{s}^{-1}(H,{\cal
A}_{S})=|\partial S|,$ namely the gaussian scrambling rate is just the number
of edges in the boundary of $S.$ Note that, generically, the solution space
(the set of dynamically selected gTPS) will be highly degenerate. For example
$\tau_{s}^{-1}(H,{\cal A}_{S})=0$ for all those $S$’s corresponding to a
disconnected component of $\cal G$ i.e. $\partial S=\emptyset.$ Or, if $\cal
G$ is a connected linear structure with two-end points the absolute minimum of
$\tau_{s}^{-1}$ (equal to one) is achieved by any connected subset $S$ of
vertices containing either one of the end points.

##  VI Conclusions

In this paper we have proposed a novel definition of generalized tensor
product structure and a dynamical mechanism for their operational emergence.
Generalized tensor product structures are defined by a dual pair $({\cal
A},\,{\cal A}^{\prime})$ made of a unital hermitian-closed subalgebra of
implementable operators $\cal A$ and its commutant ${\cal A}^{\prime}$. This
pair defines a Hilbert space mereology having both additive and tensor product
components. When $\cal A$ is factor i.e., trivial center, just the latter
survives and one has a standard virtual bipartition where the Hilbert space
becomes a simple tensor product of two subsystems associated to $\cal A$ and
${\cal A}^{\prime}$ Zanardi (2001a).

By means of a short-time expansion of the algebra OTOC recently introduced in
Zanardi (2021); Faidon Andreadakis (2022) one can define a notion of gaussian
scrambling time $\tau_{s}$ which is the time scale over which the system of
degrees of freedom associated with $\cal A$ is (approximately) mapped onto
itself and no scrambling occurs. The rate $\tau_{s}^{-1}$ has a simple and
elegant geometric meaning in terms of the distance of the system Hamiltonian
from the space ${\cal A}+{\cal A}^{\prime}$ and it involves couplings between
different central sectors and intra-sector entangling interactions.

Given the system Hamiltonian, and a family of operational possibilities, one
dynamically selects the tensor product structures corresponding to maxima of
$\tau_{s}$. In the light of the entropy-like nature of the algebra OTOC this
approach is reminiscent of the minimal entropy production principle and
selects the structures which preserves their “informational identity" the
longest. We illustrated this idea by some physically compelling examples
involving natural bipartitions, maximally abelian and stabilizer algebras.

##  VII Acknowledgments

PZ acknowledges discussions with E. Dallas and F. Andreadakis. This research
was (partially) sponsored by the Army Research Office and was accomplished
under Grant Number W911NF-20-1-0075. SL was supported by DARPA under the RQMLS
project, and by AFOSR and ARO. The views and conclusions contained in this
document are those of the authors and should not be interpreted as
representing the official policies, either expressed or implied, of the Army
Research Office or the U.S. Government. The U.S. Government is authorized to
reproduce and distribute reprints for Government purposes notwithstanding any
copyright notation herein.

## References

  * Carroll and Singh (2021) S. M. Carroll and A. Singh, Phys. Rev. A 103, 022213 (2021).
  * Zanardi (2001a) P. Zanardi, Phys. Rev. Lett. 87, 077901 (2001a).
  * Zanardi  _et al._ (2004) P. Zanardi, D. A. Lidar, and S. Lloyd, Phys. Rev. Lett. 92, 060402 (2004).
  * Zanardi and Rasetti (1997) P. Zanardi and M. Rasetti, Phys. Rev. Lett. 79, 3306 (1997).
  * Lidar  _et al._ (1998) D. A. Lidar, I. L. Chuang, and K. B. Whaley, Phys. Rev. Lett. 81, 2594 (1998).
  * Knill  _et al._ (2000) E. Knill, R. Laflamme, and L. Viola, Phys. Rev. Lett. 84, 2525 (2000).
  * Zanardi (2000) P. Zanardi, Phys. Rev. A 63, 012301 (2000).
  * Bartlett  _et al._ (2007) S. D. Bartlett, T. Rudolph, and R. W. Spekkens, Rev. Mod. Phys. 79, 555 (2007).
  * Zanardi and Lloyd (2003) P. Zanardi and S. Lloyd, Phys. Rev. Lett. 90, 067902 (2003).
  * David Kribs and Poulin (2005) R. L. David Kribs and D. Poulin, Physical review letters 94 (2005).
  * Kabernik (2018) O. Kabernik, Phys. Rev. A 97, 052130 (2018).
  * Kabernik  _et al._ (2020) O. Kabernik, J. Pollack, and A. Singh, Phys. Rev. A 101, 032303 (2020).
  * Harlow (2019) D. Harlow, Journal of High Energy Physics volume (2019).
  * Chris Akers (2019) P. R. Chris Akers, Journal of High Energy Physics volume (2019).
  * Haag (1996) R. Haag,  _Local Quantum Physics: Fields, Particles, Algebras_ , 2nd ed., Texts and Monographs in Physics (Springer, Berlin ; New York, 1996).
  * Witten (2018) E. Witten, Rev. Mod. Phys. 90, 045003 (2018).
  * Zanardi (2021) P. Zanardi, Quantum 6, 666 (2021).
  * Faidon Andreadakis (2022) P. Z. Faidon Andreadakis, Namit Anand, arXiv:2206.02033 (2022).
  * Zanardi (2001b) P. Zanardi, Physical Review A 63, 040304 (2001b).
  * Yan  _et al._ (2019) B. Yan, L. Cincio, and W. H. Zurek, arXiv:1903.02651 [quant-ph] (2019), arXiv:1903.02651 [quant-ph] .
  * Styliaris  _et al._ (2021) G. Styliaris, N. Anand, and P. Zanardi, Phys. Rev. Lett. 126, 030601 (2021).
  * Zanardi  _et al._ (2017a) P. Zanardi, G. Styliaris, and L. Campos Venuti, Physical Review A 95 (2017a), 10.1103/PhysRevA.95.052306.
  * Zanardi  _et al._ (2017b) P. Zanardi, G. Styliaris, and L. Campos Venuti, Phys. Rev. A 95, 052307 (2017b).
  * Jaynes (1980) E. Jaynes, Ann. Rev. Phys. Chem. 31, 579 (1980).
  * Zurek (1993) W. H. Zurek, Prog. Theor. Phys. 89, 281 (1993).
  * Note (1) In terms of (2) one has $\mathbb{P}_{{\cal A}}(X)=\sum@\slimits@^{\oplus}_{J}\frac{\mathbf{1}_{n_{J}}}{n_{J}}\otimes\mathrm{tr}_{n_{J}}(X),$ and $\mathbb{P}_{{\cal A}^{\prime}}(X)=\sum@\slimits@^{\oplus}_{J}\mathrm{tr}_{d_{J}}(X)\otimes\frac{\mathbf{1}_{d_{J}}}{d_{J}}.$.
  * (27) See Appendix. .
  * Note (2) For a CP map this means that the associated Krauss operators are in $\cal A$.
  * Styliaris  _et al._ (2019) G. Styliaris, N. Anand, L. C. Venuti, and P. Zanardi, Physical Review B 100, 224204 (2019), arXiv:1906.09242 .
  * Zanardi and Campos Venuti (2018) P. Zanardi and L. Campos Venuti, Journal of Mathematical Physics 59, 012203 (2018).
  * Anand  _et al._ (2021) N. Anand, G. Styliaris, M. Kumari, and P. Zanardi, Phys. Rev. Research 3, 023214 (2021).
  * Gottesman (1997) D. Gottesman, quant-ph/9705052 (1997).
  * Barnum  _et al._ (2004) H. Barnum, E. Knill, G. Ortiz, R. Somma, and L. Viola, Phys. Rev. Lett. 92, 107902 (2004).

##  Appendix A The Factor Condition

Let ${\cal A}\subset L({\cal H})$ be a unital hermitian-closed subalgebra. One
has the surjective algebra homomorphism

$\displaystyle{\cal A}\otimes{\cal A}^{\prime}\rightarrow{\cal A}\vee{\cal
A}^{\prime}:a\otimes b\mapsto ab.$ (22)

whose kernel is the ideal $\cal I$ of ${\cal A}\otimes{\cal A}^{\prime}$
generated by $\\{c\otimes\tilde{c}-\tilde{c}\otimes c\,|\,c,\tilde{c}\in{\cal
Z}({\cal A})\\}$ or, equivalently, by
$\mathrm{span}\\{\Pi_{J}\otimes\Pi_{K}-\Pi_{K}\otimes\Pi_{J}\\}_{JK}$ where
the $\Pi$’s are the central projections. Using standard isomorphisms one has
that

$\displaystyle\frac{{\cal A}\otimes{\cal A}^{\prime}}{\cal I}\cong{\cal
A}\vee{\cal A}^{\prime}.$ (23)

Since $\mathrm{dim}({\cal I})=\sum_{J\neq K}d_{J}^{2}n_{K}^{2}$ from (23) one
sees that the first isomorphism in Eq. (4) is obtained if ${\cal I}=\\{0\\}$
i.e., there is just one $J$ in Eq. (2). The latter condition means ${\cal
Z}({\cal A})=\mathbf{C}1$ which is the definition for $\cal A$ being a factor.
In this case $\mathrm{dim}({\cal A}\vee{\cal
A}^{\prime})=d_{J}^{2}n_{J}^{2}=(n_{J}d_{J})^{2}=\mathrm{dim}(L({\cal H}))$
which implies the second isomorphism in Eq. (4).

##  Appendix B $A$-OTOC and entropies: the general case

i) In Faidon Andreadakis (2022) in was proven that

$\displaystyle{G}_{{\cal A}}({\cal
U}_{t})=\frac{1}{d}\mathrm{Tr}\left[S(1-\Omega_{\cal A}){\cal
U}_{t}^{\otimes\,2}(\Omega_{{\cal
A}^{\prime}})\right]=1-\frac{1}{d}\mathrm{Tr}\left[S\Omega_{\cal A}{\cal
U}_{t}^{\otimes\,2}(\Omega_{{\cal A}^{\prime}})\right],$ (24)

where $\Omega_{\cal A}:=\mathbb{E}_{X\in{\cal A}}[X\otimes
X^{\dagger}]=\sum_{\alpha=1}^{d({\cal A})}e_{\alpha}\otimes
e^{\dagger}_{\alpha},\,$ $\Omega_{{\cal A}^{\prime}}:=\mathbb{E}_{Y\in{\cal
A}^{\prime}}[Y\otimes Y^{\dagger}]=\sum_{\beta=1}^{d({\cal
A}^{\prime})}f_{\beta}\otimes f^{\dagger}_{\beta},$ and $S$ is the swap
operator over ${\cal H}^{\otimes\,2}.$ The $e_{\alpha}$’s ($f_{\beta}$’s) form
an orthogonal (hermitean-closed) basis for $\cal A$ (${\cal A}^{\prime}$) and
fulfill Zanardi (2021); Faidon Andreadakis (2022)

$\displaystyle\mathrm{Tr}_{1}\left[S\,\Omega_{\cal
A}(X\otimes\mathbf{1})\right]=\sum_{\alpha}e_{\alpha}Xe_{\alpha}^{\dagger}=\mathbb{P}_{{\cal
A}^{\prime}}(X),\quad\mathrm{Tr}_{1}\left[S\,\Omega_{{\cal
A}^{\prime}}(X\otimes\mathbf{1})\right]=\sum_{\beta}f_{\beta}Xf_{\beta}^{\dagger}=\mathbb{P}_{{\cal
A}}(X),$ (25)

More specifically,
$e_{\alpha}=\frac{\mathbf{1}_{n_{J}}}{\sqrt{d_{J}}}\otimes|l\rangle\langle
m|,\,\alpha:=(J,l,m);\,J=1,\ldots d_{Z};\,l,m=1,\ldots,d_{J}$ and
$f_{\beta}=|p\rangle
q|\otimes\frac{\mathbf{1}_{dJ}}{\sqrt{n_{J}}},\,p,q=1,\ldots,n_{J}$ from which
it follows

$\displaystyle\Omega_{\cal A}=\sum_{\alpha}e_{\alpha}\otimes
e_{\alpha}^{\dagger}=\sum_{J}\mathbf{1}_{n_{J}}^{\otimes
2}\otimes\frac{S_{d_{J}}}{d_{J}},\quad\Omega_{{\cal
A}^{\prime}}=\sum_{\beta}f_{\beta}\otimes
f^{\dagger}_{\beta}=\sum_{J}\frac{S_{n_{J}}}{n_{J}}\otimes\mathbf{1}_{d_{J}}^{\otimes
2},$ (26)

where $S_{d_{J}}\in
L\left((\mathbf{C}^{n_{J}}\otimes\mathbf{C}^{d_{J}})^{\otimes 2}\right)$ is
the swap operators between the $\mathbf{C}^{d_{J}}$ factors (similarly for the
$S_{n_{J}}$’s.) Note that from (26) it follows
$\sum_{\alpha}\|e_{\alpha}\|_{2}^{2}=\sum_{\beta}\|f_{\beta}\|_{2}^{2}=d,$ and
$\mathrm{Tr}[\Omega_{\cal A}]=\sum_{J}n_{J}^{2}=d({\cal
A}^{\prime}),\,\mathrm{Tr}[\Omega_{{\cal
A}^{\prime}}]=\sum_{J}d_{J}^{2}=d({\cal A}).$

Using Eq. (24), (26) and $S(\mathbf{1}_{n_{J}}^{\otimes 2}\otimes
S_{d_{J}})=S_{n_{J}}\otimes\mathbf{1}_{d_{J}}^{\otimes 2},$ one gets the
following expression for the $\cal A$-OTOC

$\displaystyle 1-G_{{\cal A}}({\cal
U})=\frac{1}{d}\sum_{JK}\frac{1}{n_{K}d_{J}}\mathrm{Tr}\left[({S_{n_{J}}}\otimes\mathbf{1}_{d_{J}}^{\otimes
2})\,{\cal U}_{JK}^{\otimes 2}({S_{n_{K}}}\otimes\mathbf{1}_{d_{K}}^{\otimes
2})\right],$ (27)

where ${\cal U}_{JK}(X):=(\Pi_{J}U\Pi_{K})X(\Pi_{J}U\Pi_{K})^{\dagger}.$ For
the factor case $d_{Z}=1$ one recovers the bipartite OTOC ( i.e., operator
entanglement of $U$) (8) while for abelian ${\cal A}^{\prime}$
($n_{K}=1,\forall K)$ one finds:

$\displaystyle 1-G_{{\cal A}}({\cal
U})=\frac{1}{d}\sum_{J}\frac{1}{d_{J}}\sum_{K}\mathrm{Tr}\left[\Pi_{J}^{\otimes
2}{\cal U}(\Pi_{K})^{\otimes
2}\right]=\sum_{J}q_{J}\sum_{K}|\langle\frac{\Pi_{J}}{d_{J}},\,{\cal
U}(\Pi_{K})\rangle|^{2}=\sum_{J}q_{J}\|\mathbf{p}_{J}\|^{2}$ (28)

where $q_{J}:=\frac{d_{J}}{d_{J}}$ and
$\mathbf{p}_{J}:=(\langle\frac{\Pi_{J}}{d_{J}},\,{\cal
U}(\Pi_{K})\rangle)_{K=1}^{d_{Z}}$ are probability vectors as
$(\mathbf{p}_{J})_{K}\geq 0$ and
$\sum_{K}(\mathbf{p}_{J})_{K}=\mathrm{Tr}[\frac{\Pi_{J}}{d_{J}}{\cal
U}(\sum_{K}\Pi_{K})]=\mathrm{Tr}[\frac{\Pi_{J}}{d_{J}}]=1.$ Then, using
$\sum_{J}q_{J}=\frac{1}{d}\sum_{J}d_{J}=1$ one obtains (11).

More in general, the term in (27) under trace can be seen to be proportional
to the operator purity of the maps $U_{JK}:=\Pi_{J}U\Pi_{K}:{\cal
H}_{K}\cong\mathbf{C}^{n_{K}}\otimes\mathbf{C}^{d_{K}}\rightarrow{\cal
H}_{J}\cong\mathbf{C}^{n_{J}}\otimes\mathbf{C}^{d_{J}}.$ The entropic
contributions to (27) are an intertwining of the “uniformization" of the the
central sector system (due to the the "off-diagonal" $U_{JK}$ for $J\neq K$)
and the operator entanglement of the individual $U_{JK}.$ Both the additive
and the multiplicative mereological structures contribute to the $A$-OTOC
entropic nature.

##  Appendix C Proof of the Proposition.

i) If ${\cal U}_{t}=e^{it{\cal H}}$ by expanding the exponential one finds
that the zeroth and first order terms vanish and $G_{{\cal A}}({\cal
U}_{t})=\frac{t^{2}}{d}\mathrm{Tr}\left[(S(\Omega_{\cal A}-\mathbf{1}){\cal
H}^{\otimes\,2}(\Omega_{{\cal A}^{\prime}})\right]+O(t^{3}).$ Now ${\cal
H}(X)=HX-XH:=(L_{H}-R_{H})(X)$ and therefore ${\cal H}^{\otimes
2}=L_{H}^{\otimes 2}-L_{H}\otimes R_{H}-R_{H}\otimes L_{H}+R_{H}^{\otimes 2}.$
Computations using Eq. (25) and $\mathrm{Tr}\left[S(A\otimes
B)\right]=\mathrm{Tr}[AB]$ lead to

$\displaystyle\mathrm{Tr}\left[S\,\Omega_{\cal
A}{R_{H}}^{\otimes\,2}(\Omega_{{\cal
A}^{\prime}})\right]=\mathrm{Tr}\left[S\,\Omega_{\cal
A}{L_{H}}^{\otimes\,2}(\Omega_{{\cal
A}^{\prime}})\right]=\langle\mathbb{P}_{\cal A}(H),\mathbb{P}_{{\cal
A}^{\prime}}(H)\rangle.$ (29)

and

$\displaystyle\mathrm{Tr}\left[S\,\Omega_{\cal A}({R_{H}}\otimes
L_{H})(\Omega_{{\cal A}^{\prime}})\right]=\mathrm{Tr}\left[S\,\Omega_{\cal
A}({L_{H}}\otimes R_{H})(\Omega_{{\cal
A}^{\prime}})\right]=\|\mathbb{P}_{{\cal
A}^{\prime}}(H)\|_{2}^{2},\quad\mathrm{Tr}\left[S{\cal H}^{\otimes
2}(\Omega_{{\cal A}^{\prime}}\right]=\|\mathbb{P}_{{\cal
A}}(H)\|_{2}^{2}-\|H\|_{2}^{2}.$ (30)

Bringing all terms together (and up to higher order terms)

$\displaystyle G_{{\cal A}}({\cal
U}_{t})=\frac{2t^{2}}{d}\left(\|H\|_{2}^{2}-\|\mathbb{P}_{{\cal
A}^{\prime}}(H)\|_{2}^{2}+\langle\mathbb{P}_{\cal A}(H),\mathbb{P}_{{\cal
A}^{\prime}}(H)\rangle-\|\mathbb{P}_{{\cal A}}(H)\|_{2}^{2}\right)\rangle$
$\displaystyle=\frac{2t^{2}}{d}\langle H,(1-\mathbb{P}_{{\cal
A}})(1-\mathbb{P}_{{\cal
A}^{\prime}})(H))\rangle=\frac{2t^{2}}{d}\|(1-\mathbb{P}_{{\cal
A}})(1-\mathbb{P}_{{\cal A}^{\prime}})(H)\|_{2}^{2}.$ (31)

Now $\mathbb{P}_{{\cal A}+{\cal A}^{\prime}}=\mathbb{P}_{{\cal
A}}+\mathbb{P}_{{\cal A}^{\prime}}-\mathbb{P}_{{\cal A}}\mathbb{P}_{{\cal
A}^{\prime}}$ and $1-\mathbb{P}_{{\cal A}+{\cal
A}^{\prime}}=(1-\mathbb{P}_{{\cal A}})(1-\mathbb{P}_{{\cal A}^{\prime}})$ from
which Eq. (13) follows. ii) if $H\in{\cal A}+{\cal A}^{\prime}$ the ${\cal
U}_{t}$ factorizes in two commuting unitaries, one acting on $\cal A$ and the
other on ${\cal A}^{\prime}.$ Plugging this into the definition (6) one sees
that ${\cal U}(Y)\in{\cal A}^{\prime}$ and that the $\cal A$-OTOC then
vanishes. Viceversa, if the $\cal A$-OTOC is identically zero then also
$\tau^{-1}_{s}=0$ which, by Eq. (13), is possible iff $H=\mathbb{P}_{{\cal
A}+{\cal A}^{\prime}}(H)$ i.e., $H\in{\cal A}+{\cal A}^{\prime}.$ iii) Just
use $D(x,W)=\inf_{y\in W}\|x-y\|=\|(1-P_{W})x\|.$ Where $P_{W}$ is the
subspace projection. iv) One has that $\|(1-\mathbb{P}_{{\cal
A}})(1-\mathbb{P}_{{\cal A}^{\prime}})(H)\|_{2}\leq\|(1-\mathbb{P}_{{\cal
A}})(H)\|_{2}=D(H,{\cal A})$ and $\|(1-\mathbb{P}_{{\cal
A}})(1-\mathbb{P}_{{\cal A}^{\prime}})(H)\|_{2}\leq\|(1-\mathbb{P}_{{\cal
A}^{\prime}})(H)\|_{2}=D(H,{\cal A}^{\prime})$ from which the bound (15)
follows. v) Since ${\cal A}+{\cal A}^{\prime}\subset{\cal A}\vee{\cal
A}^{\prime},$ one has the identity $1-\mathbb{P}_{{\cal A}+{\cal
A}^{\prime}}=(1-\mathbb{P}_{{\cal A}\vee{\cal A}^{\prime}})+\mathbb{P}_{{\cal
A}\vee{\cal A}^{\prime}}(1-\mathbb{P}_{{\cal A}+{\cal A}^{\prime}})$ one also
finds

$\displaystyle\tau^{-2}_{s}(H,{\cal A})=\|(1-\mathbb{P}_{{\cal A}\vee{\cal
A}^{\prime}})(\tilde{H})\|_{2}^{2}+\|\mathbb{P}_{{\cal A}\vee{\cal
A}^{\prime}}(1-\mathbb{P}_{{\cal A}+{\cal A}^{\prime}})(\tilde{H})\|_{2}^{2}.$
(32)

Since $\mathbb{P}_{{\cal A}\vee{\cal A}^{\prime}}(X)=\sum_{J}\Pi_{J}X\Pi_{J}$
where the $\Pi_{J}$’s are the central projections in (2), the first term can
be written $\sum_{J}\|\Pi_{J}H(1-\Pi_{J})\|_{2}^{2}$ whereas the second term
is a sum over $J$ of terms as in Eq. (17) squared. The rate is given by two
different types of contributions: coupling between different central sectors
${\cal H}_{J}\cong\mathbf{C}^{n}_{J}\otimes\mathbf{C}^{d_{J}}$ in (2) and
entangling “interactions" inside each of them. When either $\cal A$ or ${\cal
A}^{\prime}$ is Abelian the second contribution vanishes ( ${\cal
A}\subset{\cal A}^{\prime}$ or ${\cal A}^{\prime}\subset{\cal A}$ implies
${\cal A}+{\cal A}^{\prime}={\cal A}\vee{\cal A}^{\prime}$) and one obtains
(16).

##  Appendix D Proof of Eq. (18)

The distance between two maximal abelian algebras ${\cal
A}_{B}=\mathbb{C}\\{|i\rangle\langle i|\\}$ and ${\cal
A}_{\tilde{B}}=\mathbb{C}\\{|\tilde{i}\rangle\langle\tilde{i}|\\}$ is given by
$D({\cal A}_{B},{\cal A}_{\tilde{B}})=\|\mathbb{P}_{{\cal
A}_{B}}-\mathbb{P}_{{\cal
A}_{\tilde{B}}}\|_{HS}=\sqrt{2d(1-\frac{1}{d}\sum_{i,\tilde{i}}|\langle
i|\tilde{i}\rangle|^{4})}=\sqrt{2d(1-\mathrm{tr}(X^{T}X))}$ where
$X_{i,j}:=|\langle i|\tilde{j}\rangle|^{2}$ Zanardi and Campos Venuti (2018).
From (16)

$1/\tau_{s}^{2}(H,{\cal A}_{B})=\frac{1}{d}\sum_{i=1}^{d}(\langle
i|H^{2}|i\rangle-\langle
i|H|i\rangle^{2})=\eta_{H}^{2}(1-\langle\mathbf{\varepsilon},X_{H}^{T}X_{H}\varepsilon\rangle),\quad\eta_{H}:=\frac{\|H\|_{2}}{\sqrt{d}}$

where $H=\sum_{k}\tilde{\epsilon}_{k}|\tilde{k}\rangle\langle\tilde{k}|$ is
the spectral resolution of $H,$ the normalized vector
$\varepsilon=\frac{1}{\|H\|_{2}}(\tilde{\epsilon}_{1},\ldots,\tilde{\epsilon}_{d}),$
and $(X_{H})_{ik}:=|\langle i|\tilde{k}\rangle|^{2}.$ Then
$\tau_{s}^{-2}\leq\eta_{H}^{2}\|1-X_{H}^{T}X_{H}\|_{\infty}\leq\eta_{H}^{2}\,\|1-X_{H}^{T}X_{H}\|_{1}=\eta_{H}^{2}\,\mathrm{tr}\left(1-X_{H}^{T}X_{H}\right)=d\
\eta_{H}^{2}\,\left(1-\frac{1}{d}\mathrm{tr}(X_{H}^{T}X_{H})\right)=\frac{1}{2}\eta_{H}^{2}\,D^{2}({\cal
A}_{B},{\cal A}_{B_{H}}),$ whence $\tau_{s}^{-1}\leq{\eta_{H}}\,D({\cal
A}_{B},{\cal A}_{B_{H}}).$

##  Appendix E Proof of Eq. (20)

By definition ${\cal U}({\cal A}):=\\{UxU^{\dagger}\,|\,x\in{\cal A}\\}$ for
unitary $U$ is a unital hermitian-closed subalgebra of $L({\cal H})$ if ${\cal
A}$ is so. Then, $\mathbb{P}_{{\cal U}({\cal A})}={\cal U}\mathbb{P}_{{\cal
A}}{\cal U}^{\dagger}$ by direct inspection. The same relation is true for
$({\cal U}({\cal A}))^{\prime}={\cal U}({\cal A}^{\prime})$ i.e.,
$\mathbb{P}_{U{\cal A}^{\prime}U^{\dagger}}={\cal U}\mathbb{P}_{{\cal
A}^{\prime}}{\cal U}^{\dagger}$ Using unitary invariance of $\|\cdot\|_{2}$
one finds:

$\displaystyle\tau_{s}^{-1}(H,{\cal U}({\cal A}))=\|(1-\mathbb{P}_{{\cal
U}({\cal A}^{\prime})})(1-\mathbb{P}_{{\cal U}({\cal A})})(H)\|_{2}=\|{\cal
U}(1-\mathbb{P}_{{\cal A}^{\prime}}){\cal U}^{\dagger}{\cal
U}(1-\mathbb{P}_{{\cal A}}){\cal U}^{\dagger}(H)\|_{2}$
$\displaystyle=\|(1-\mathbb{P}_{{\cal A}^{\prime}})(1-\mathbb{P}_{{\cal
A}}){\cal U}^{\dagger}(H)\|_{2}=\tau_{s}^{-1}({\cal U}^{\dagger}(H),{\cal
A}).$ (33)


# On Consistency of Graph-based Semi-supervised Learning

Chengan Du and Yunpeng Zhao
Department of Statistics
George Mason University

(Mar 17, 2017)

###### Abstract

Graph-based semi-supervised learning is one of the most popular methods in
machine learning. Some of its theoretical properties such as bounds for the
generalization error and the convergence of the graph Laplacian regularizer
have been studied in computer science and statistics literatures. However, a
fundamental statistical property, the consistency of the estimator from this
method has not been proved. In this article, we study the consistency problem
under a non-parametric framework. We prove the consistency of graph-based
learning in the case that the estimated scores are enforced to be equal to the
observed responses for the labeled data. The sample sizes of both labeled and
unlabeled data are allowed to grow in this result. When the estimated scores
are not required to be equal to the observed responses, a tuning parameter is
used to balance the loss function and the graph Laplacian regularizer. We give
a counterexample demonstrating that the estimator for this case can be
inconsistent. The theoretical findings are supported by numerical studies.

##  1 Introduction

Semi-supervised learning is a class of machine learning methods that stand in
the middle ground between supervised learning in which all training data are
labeled, and unsupervised learning in which no training data are labeled.
Specifically, in addition to the labeled training data $X_{1},\dots,X_{n}$,
there exist unlabeled inputs $X_{n+1},\dots,X_{n+m}$. Under certain
assumptions on the geometric structure of the input data, such as the cluster
assumption or the low-dimensional manifold assumption [7], the use of both
labeled and unlabeled data can achieve better prediction accuracy than
supervised learning that only uses labeled inputs $X_{1},\dots,X_{n}$.

Semi-supervised learning has become popular since the acquisition of unlabeled
data is relatively inexpensive. A large number of methods were developed under
the framework of semi-supervised learning. For example, [18] proposed that the
combination of labeled and unlabeled data will improve the prediction accuracy
under the assumption of mixture models. The self-training method [19] and the
co-training method [13] were soon applied to semi-supervised learning when
mixture models are not assumed. [23] described an approach to semi-supervised
clustering based on hidden Markov random fields (HMRFs) that can combine
multiple approaches in a unified probabilistic framework. [1] proposed a
probabilistic framework for semi-supervised learning incorporating a K-means
type hard partition clustering algorithm (HMRF-Kmeans). [20] proposed the
transductive support vector machines (TSVMs) that used the idea of
transductive learning by including unlabeled data in the computation of the
margin. Transductive learning is a variant of semi-supervised learning which
focuses on the inference of the correct labels for the given unlabeled data
other than the inference of the general rule. [4] used a convex relaxation of
the optimization problem called semi-definite programming as a different
approaches to the TSVMs.

In this article, we focus on a particular semi-supervised method – graph-based
semi-supervised learning. In this method, the geometric structure of the input
data are represented by a graph $G=(V,E)$, where nodes
$V=\\{v_{1},\dots,v_{n+m}\\}$ represent the inputs and edges $E$ represent the
similarities between them. The similarities are given in an $n+m$ by $n+m$
symmetric similarity matrix (or called kernel matrix), $W=[w_{ij}]$, where
$0\leq w_{ij}\leq 1$. The larger $w_{ij}$ implies that $X_{i}$ and $X_{j}$ are
more similar. Further, let $Y_{1},\dots,Y_{n}$ be the responses of the labeled
data.

[25] proposed the following graph-based learning method,

$\displaystyle\min_{\boldsymbol{f}=(f_{1},\dots,f_{n+m})^{T}}\sum_{i=1}^{n+m}\sum_{j=1}^{n+m}w_{ij}(f_{i}-f_{j})^{2}$
(1)

subject to $f_{i}=Y_{i},i=1,\dots,n$.

Its solution is called the estimated scores. The objective function (1) (named
“hard criterion” thereafter), requires all the estimated score to be exactly
the same as the responses for the labeled data. [8] relaxed this requirement
by proposing a soft version (named “soft criterion” thereafter). We follow an
equivalent form given in [26],

$\displaystyle\min_{\boldsymbol{f}=(f_{1},\dots,f_{n+m})^{T}}\sum_{i=1}^{n}(Y_{i}-f_{i})^{2}+\frac{\lambda}{2}\sum_{i=1}^{n+m}\sum_{j=1}^{n+m}w_{ij}(f_{i}-f_{j})^{2}.$
(2)

The soft criterion belongs to the “loss+penalty” paradigm: It searches for the
minimizer $\boldsymbol{\hat{f}}$ which achieves a small training error, and in
the meanwhile imposes the smoothness on $\boldsymbol{\hat{f}}$ by a penalty
based on similarity matrix. It can be easily seen that when $\lambda=0$ the
soft criterion is equivalent to the hard criterion.

  * Remark

The tuning parameter $\lambda$ being 0 in the soft criterion (2) is understood
in the following sense: The squared loss has infinite weight and thereby
$Y_{i}=f_{i}$ for all labeled data. But
$\sum_{i=1}^{n+m}\sum_{j=1}^{n+m}w_{ij}(f_{i}-f_{j})^{2}$ still plays a
crucial role when it has no conflict with the hard constraints on the labeled
data, that is, it provides links between $f_{i}$’s on the labeled and
unlabeled data. Therefore, the soft criterion (2) at $\lambda=0$ becomes the
hard criterion (1).

Researchers have proposed different variants of graph-based learning methods,
such as [24] and [2]. We only focus on (1) and (2) in this article.

The theoretical properties of graph-based learning have been studied in
computer science and statistics literatures. [5] derived the limit of the
Laplacian regularizer when the sample size of unlabeled data goes to infinity.
[11] considered the convergence of Laplacian regularizer on Riemannian
manifolds. [3] reinterpretted the graph Laplacian as a measure of intrinsic
distances between inputs on a manifold and reformulated the problem as a
functional optimization in a reproducing kernel Hilbert space. [16] pointed
out that the hard criterion can yield completely noninformative solution when
the size of unlabeled data goes to infinity and labeled data are finite, that
is, the solution can give a perfect fit on the labeled data but remains as 0
on the unlabeled data. [14] obtained the asymptotic mean squared error of a
different version of graph-based learning criterion. [2] gave a bound of the
generalization error for a slightly different version of (2).

But to the best of our knowledge, no result is available in literature on a
very fundamental question – the consistency of graph-based learning, which is
the main focus of this article. Specifically, we want to answer the question
that under what conditions $\hat{f}_{i}$ will converge to
$\mathbb{E}[Y_{i}|X_{i}]$ on unlabeled data, where $\mathbb{E}[Y_{i}|X_{i}]$
is the true probability of a positive label given $X_{i}$ if responses are
binary, and $\mathbb{E}[Y_{i}|X_{i}]$ is the regression function on $X_{i}$ if
responses are continuous. We will always call $\mathbb{E}[Y_{i}|X_{i}]$ as
regression function for simplicity.

Most of the literatures discussed above considered a “functional version” of
(1) and (2). They used a functional optimization problem with the optimizer
$\hat{f}(x)$ being a function, as an approximation of the original problem
with the optimizer $\boldsymbol{\hat{f}}$ being a vector. And they studied the
behavior of the limit of graph Laplacian and the solution $\hat{f}(x)$. We do
not adopt this framework but use a more direct approach. We focus on the
original problem and study the relations of $\hat{f}_{i}$ and
$\mathbb{E}[Y_{i}|X_{i}]$ under the general non-parametric setting. Our
approach essentially belongs to the framework of transductive learning, which
focuses on the prediction on the given unlabeled data $X_{n+1},\dots,X_{n+m}$,
not the general mapping from inputs to responses. By establishing a link
between the optimizer of (1) and the Nadaraya-Watson estimator [15, 21] for
kernel regression, we will prove the consistency of the hard criterion. The
theorem allows both $m$ and $n$ to grow. On the other hand, we show that the
soft criterion is inconsistent for sufficiently large $\lambda$. To the best
of our knowledge, this is the first result that explicitly distinguishes the
hard criterion and the soft criterion of graph-based learning from a
theoretical perspective and shows that they have very different asymptotic
behaviors.

The rest of the article is organized as follows. In Section 2, we state the
consistency result for the hard criterion and give the counterexample for the
soft criterion. We prove the consistency result in Section 3. Numerical
studies in Section 4 support our theoretical findings. Section 5 concludes
with a summary and discussion of future research directions.

##  2 Main Results

We begin with basic notation and setup. Let
$(X_{1},Y_{1}),\dots,(X_{n+m},Y_{n+m})$ be independently and identically
distributed pairs. Here each $X_{i}$ is a $d$-dimensional vector and
$\boldsymbol{Y}=(Y_{1},\dots,Y_{n+m})^{T}$ are binary responses labeled as 1
and 0 (the classification case) or continuous responses (the regression case).
The last $m$ responses are unobserved.

[25] used a fixed point algorithm to solve the hard criterion (1), which is

$\displaystyle
f_{a}=\frac{\sum_{i=1}^{n+m}w_{ak}f_{i}}{\sum_{i=1}^{n+m}w_{ai}},\quad
a=n+1,\dots,n+m.$ (3)

Note that (3) is not a closed-form solution but an updating formula for the
iterative algorithm, since its right-hand side depends on unknown quantities.

In order to obtain a closed-form solution for (1), we begin by solving the
soft version (2) and then let $\lambda=0$. Recall that $W$ is the similarity
matrix. Let $D=\textnormal{diag}(d_{1},\dots,d_{n+m})$ where
$d_{i}=\sum\limits_{j=1}^{n+m}w_{ij}$, and $L=D-W$ being the unnormalized
graph Laplacian (see [17] for more details). Soft criterion (2) can be written
in matrix form

$\displaystyle\min_{\boldsymbol{f}}\sum_{i=1}^{n}(\boldsymbol{f}-\boldsymbol{Y}_{n})^{T}(\boldsymbol{f}-\boldsymbol{Y}_{n})+\lambda\boldsymbol{f}^{T}L\boldsymbol{f},$
(4)

where $\boldsymbol{Y}_{n}=(Y_{1},\dots,Y_{n})^{T}$. Further, let $V$ be an
$n+m$ by $n+m$ matrix defined as

$\displaystyle V$ $\displaystyle=\begin{pmatrix}I_{n}&\boldsymbol{0}\\\
\boldsymbol{0}&\boldsymbol{0}\end{pmatrix}.$

Then by taking the derivative of (4) with respect to $\boldsymbol{f}$ and
setting equal to zero, we obtain the solution as follows,

$\displaystyle\boldsymbol{\hat{f}}$ $\displaystyle=(V+\lambda
L)^{-1}V\begin{pmatrix}\boldsymbol{Y}_{n}\\\ \boldsymbol{0}\end{pmatrix}.$

What we are interested in are the estimated scores on the unlabeled data, i.e.
$\boldsymbol{\hat{f}}_{(n+1):(n+m)}=(\hat{f}_{n+1},\dots,\hat{f}_{n+m})^{T}$.
In order to obtain an explicit form for $\boldsymbol{\hat{f}}_{(n+1):(n+m)}$,
we use a formula for inverse of a block matrix (see standard textbooks on
matrix algebra such as [12] for more details): For any non-singular square
matrix $A$

$\displaystyle A=\begin{pmatrix}A_{11}&A_{12}\\\ A_{21}&A_{22}\end{pmatrix},$
$\displaystyle
A^{-1}=\begin{pmatrix}(A_{11}-A_{12}A_{22}^{-1}A_{21})^{-1}&-(A_{11}-A_{12}A_{22}^{-1}A_{21})^{-1}A_{12}A_{22}^{-1}\\\
-(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}A_{21}A_{11}^{-1}&(A_{22}-A_{21}A_{11}^{-1}A_{12})^{-1}\end{pmatrix}.$

Write $D$ and $W$ as $2\times 2$ block matrices,

$\displaystyle D=\begin{pmatrix}D_{11}&D_{12}\\\
D_{21}&D_{22}\end{pmatrix},W=\begin{pmatrix}W_{11}&W_{12}\\\
W_{21}&W_{22}\end{pmatrix}.$

By the formula above,

$\displaystyle\boldsymbol{\hat{f}}_{(n+1):(n+m)}=$
$\displaystyle(D_{22}-W_{22}-\lambda W_{21}(I_{n}+\lambda D_{11}-\lambda
W_{11})^{-1}W_{12})^{-1}W_{21}(I_{n}+\lambda D_{11}-\lambda
W_{11})^{-1}\boldsymbol{Y}_{n}.$ (5)

Letting $\lambda=0$, we obtain the solution for the hard criterion (1),

$\displaystyle\boldsymbol{\hat{f}}_{(n+1):(n+m)}=(D_{22}-W_{22})^{-1}W_{21}\boldsymbol{Y}_{n}.$
(6)

[2] obtained a similar formula for a slightly different objective function.

Clearly, the form of (6) is closely related to the Nadaraya-Watson estimator
[15],[21] for kernel regression, which is

$\displaystyle\hat{q}_{n+a}=\frac{\sum_{i=1}^{n}w_{n+a,i}Y_{i}}{\sum_{k=1}^{n}w_{n+a,i}},\quad
a=1,\dots,m.$ (7)

The Nadaraya-Watson estimator is well studied under the non-parametric
framework. We can construct $W$ by a kernel function, that is, let
$w_{ij}=K((X_{i}-X_{j})/h_{n})$, where $K$ is a nonnegative function on
$\mathbb{R}^{d}$, and $h_{n}$ is a positive constant controlling the bandwidth
of the kernel. Let $q(X)=\mathbb{E}[Y|X]$ be the true regression function. The
consistency of Nadaraya-Watson estimator was first proved by [21] and [15].
And many other researchers such as [9] and [6] studied its asymptotic
properties under different assumptions. Here we follow the result in [10]. If
$h_{n}\to 0$, $nh_{n}^{d}\to\infty$ as $n\to\infty$, and $K$ satisfies:

  * (i)

$K$ is bounded by $k^{*}<\infty$;

  * (ii)

The support of $K$ is compact;

  * (iii)

$K\geq\beta I_{B}$ for some $\beta>0$ and some closed ball $B$ centered at the
origin and having positive radius $\delta$,

then $\hat{q}_{n+a}$ converges to $q(X_{n+a})$ in probability for
$a=1,\dots,m$.

By establishing a connection between the solution of the hard criterion and
Nadaraya-Watson estimator, we prove the following main theorem:

######  Theorem 1.

Suppose that $(X_{1},Y_{1}),(X_{2},Y_{2}),\dots,(X_{n+m},Y_{n+m})$ are
independently and identically distributed with $Y_{i}$ being bounded; $h_{n}$
and $K$ satisfy the above conditions. Further, let $Z$ be the difference of
two independent $X$’s, i.e. $Z=X_{1}-X_{2}$, with probability density function
$g_{Z}(z)$. Assume that there exists $c>0$, such that for any $\Delta\leq c$,

$\displaystyle\min\limits_{\|z\|\leq\Delta}g_{Z}(z)=e>0.$ (8)

Then, for $m=o(nh_{n}^{d})$, $\hat{f}_{n+a}$ given in (5) converges to
$q(X_{n+a})$ in probability, for $a=1,\dots,m$.

The proof will be given in Section 3.

  * Remark

Theorem 1 established the consistency of the hard criterion under the standard
non-parametric framework with two additional assumptions. Firstly, both
labeled data and unlabeled data are allowed to grow but the size of unlabeled
data $m$ grows slower than the size of labeled data $n$. We conjecture that
when $m$ grows faster than $n$, the graph-based semi-supervised learning may
not be consistent based on the simulation studies in Section 4. [16] also
suggested that the method may not work when $m$ grows too fast. Secondly, we
assume that density function of the difference of two independent inputs is
strictly positive near the origin, which is a mild technical condition valid
for commonly used density functions.

Theorem 1 provides some surprising insights about the hard criterion of graph-
based learning. At a first glance, the hard criterion makes an impractical
assumption that requires the responses to be noiseless, while the soft
criterion seems to be a more natural choice. But according to our theoretical
analysis, the hard criterion is consistent under the standard non-parametric
framework where the responses on training data are of course allowed to be
random and noisy.

We now consider the soft criterion with $\lambda\neq 0$.

######  Proposition 2.

Suppose that $(X_{1},Y_{1}),(X_{2},Y_{2}),\dots,(X_{n+m},Y_{n+m})$ are
independently and identically distributed with $|\mathbb{E}(Y_{1})|<\infty$.
Further, suppose that $W$ represents a connected graph. Then for sufficiently
large $\lambda$, the soft criterion (2) is inconsistent.

###### Proof.

Consider another extreme case of the soft criterion (2), $\lambda=\infty$.
When $W$ represents a connected graph, the objective function becomes

$\displaystyle\min_{\boldsymbol{f}=(f_{1},\dots,f_{n})^{T}}\sum_{i=1}^{n}(Y_{i}-f_{i})^{2}$
(9)

subject to $f_{i}=f_{j},1\leq i,j\leq n+m$.

It is easy to check that the solution of (9), denoted by
$\boldsymbol{\hat{f}}(\infty)$, is given by

$\displaystyle\hat{f}_{n+a}(\infty)=\frac{1}{n}\sum_{i=1}^{n}Y_{i},\,\,a=1,\dots,m.$

By the law of large numbers,

$\displaystyle\lim_{n\to\infty}\hat{f}_{n+a}(\infty)=\mathbb{E}[q(X_{1})]\,\,\mbox{almost
surely}.$

Clearly, $\mathbb{E}[q(X_{1})]\neq q(X_{n+a})$ since the right-hand side is a
random variable. This implies that for sufficiently large $\lambda$, the soft
criterion is inconsistent. ∎

##  3 Proof of the Main Theorem

We give the proof of Theorem 1 in this section.

Recall that

$\displaystyle\boldsymbol{\hat{f}}_{(n+1):(n+m)}=(D_{22}-W_{22})^{-1}W_{21}\boldsymbol{Y}_{n}.$

We first focus on $(D_{22}-W_{22})^{-1}$. Clearly,

$\displaystyle(D_{22}-W_{22})^{-1}=(I_{m}-D_{22}^{-1}W_{22})^{-1}D_{22}^{-1}.$

For any positive integer $l$, define

$\displaystyle
S_{l}=D_{22}^{-1}W_{22}+(D_{22}^{-1}W_{22})^{2}+(D_{22}^{-1}W_{22})^{3}+\dots+(D_{22}^{-1}W_{22})^{l}.$

Our goal is to prove that the limit of $S_{l}$ exists with probability
approaching 1, and thus we can have

$\displaystyle(I_{m}-D_{22}^{-1}W_{22})^{-1}=I_{m}+\lim_{l\to\infty}S_{l}$

with probability approaching 1 [22].

By definition,

$D_{22}=\left({\begin{array}[]{*{20}c}d_{n+1,n+1}&\cdots&0\\\
\vdots&\ddots&\vdots\\\ 0&\cdots&d_{n+m,n+m}\end{array}}\right),$
$W_{22}=\left({\begin{array}[]{*{20}c}w_{n+1,n+1}&\cdots&w_{n+1,n+m}\\\
\vdots&\ddots&\vdots\\\ w_{n+m,n+1}&\cdots&w_{n+m,n+m}\end{array}}\right),$
where

$\displaystyle d_{n+a,n+a}=\sum\limits_{k=1}^{n+m}w_{n+a,k},\quad
w_{n+a,i}=K\left(\frac{X_{n+a}-X_{i}}{h_{n}}\right),$

for $1\leq a\leq m,1\leq i\leq n+m$. Thus we have

$D_{22}^{-1}W_{22}=\left({\begin{array}[]{*{20}c}w_{n+1,n+1}/d_{n+1,n+1}&\cdots&w_{n+1,n+m}/d_{n+1,n+1}\\\
\vdots&\ddots&\vdots\\\
w_{n+1,n+m}/d_{n+m,n+m}&\cdots&w_{n+m,n+m}/d_{n+m,n+m}\end{array}}\right).$

Since $h_{n}\to 0$, there exist $n_{0}\in\mathbb{N}$, such that $\delta
h_{n}\leq c$ holds for every $n>n_{0}$. Thus by the assumption in (8), for
$1\leq a\leq m$ and $1\leq i\leq n$,

$\displaystyle p_{n}$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}\mathbb{E}(I\\{\|X_{i}-X_{n+a}\|\leq\delta
h_{n}\\})$ $\displaystyle=\mathbb{P}(\|Z\|\leq\delta
h_{n})=\int\limits_{\|z\|\leq\delta h_{n}}g_{Z}(z)\mu dz\geq eV_{d}(\delta
h_{n})=sh_{n}^{d},$

where $V_{d}(\delta h_{n})$ denotes the volume of a $d$-dimensional ball with
radius $h_{n}$, and $s$ is a constant independent with $n$. Since
$nh_{n}^{d}\to\infty$, the above inequality implies $np_{n}\to\infty$. On the
other side, $p_{n}\to 0$ since $h_{n}\to 0$.

Further,

$\displaystyle\text{Var}(I\\{\|X_{i}-X_{n+a}\|\leq\delta
h_{n}\\})=p_{n}(1-p_{n}).$

By Chebyshev’s Inequality, for any $0<\epsilon<1/2$, since
$nh_{n}^{d}\to\infty$,

$\displaystyle\mathbb{P}\left(\left|\frac{\sum_{i=1}^{n}I\\{\|X_{i}-X_{n+a}\|\leq\delta
h_{n}\\}}{np_{n}}-1\right|\geq\epsilon\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\left|\frac{1}{n}\sum\limits_{i=1}^{n}I\\{\|X_{i}-X_{n+a}\|\leq\delta
h_{n}\\}-p_{n}\right|\geq\epsilon p_{n}\right)$ $\displaystyle\leq$
$\displaystyle\frac{p_{n}(1-p_{n})}{n\epsilon^{2}p_{n}^{2}}\leq\frac{1}{\epsilon^{2}p_{n}n}\leq\frac{1}{\epsilon^{2}snh_{n}^{d}}\to
0\quad\textnormal{as }n\to\infty.$ (10)

This further implies

$\displaystyle\frac{\sum\limits_{i=1}^{n}I\\{\|X_{i}-X_{n+a}\|\leq\delta
h_{n}\\}}{np_{n}}\to 1\quad\textnormal{in probability.}$

We now continue to study the property of $D_{22}^{-1}W_{22}$. Consider each
element $(D_{22}^{-1}W_{22})_{ab}$ of this matrix. For $1\leq a,b\leq m$,

$\displaystyle(D_{22}^{-1}W_{22})_{ab}$
$\displaystyle=\frac{w_{n+a,n+b}}{d_{n+a,n+a}}=K\left(\frac{X_{n+a}-X_{n+b}}{h_{n}}\right)/\sum\limits_{i=1}^{n+m}K\left(\frac{X_{i}-X_{n+a}}{h_{n}}\right)$
$\displaystyle\leq\frac{k^{*}}{\beta\sum\limits_{i=1}^{n}I\\{\|X_{i}-X_{n+a}\|\leq\delta
h_{n}\\}},$

by condition (i) and (iii). For simplicity of notation, let

$\Phi_{n}(a)=\frac{\sum\limits_{i=1}^{n}I\\{\|X_{i}-X_{n+a}\|\leq\delta
h_{n}\\}}{np_{n}},$

where $\Phi_{n}$ is a nonnegative function depending on $n$. Thus
$\frac{k^{*}}{\beta\Phi_{n}(a)np_{n}}$ is an upper bound of every element in
the matrix $D_{22}^{-1}W_{22}$. By (10), we have

$\displaystyle\mathbb{P}(0\leq\Phi_{n}(a)\leq
1-\epsilon)\leq\mathbb{P}(|\Phi_{n}(a)-1|\geq\epsilon)\leq\frac{1}{\epsilon^{2}snh_{n}^{d}},$

which implies

$\displaystyle\mathbb{P}\left(\min_{1\leq a\leq m}\Phi_{n}(a)\leq
1-\epsilon\right)$
$\displaystyle=\mathbb{P}\left(\bigcup\limits_{a=1}^{m}\\{\Phi_{n}(a)\leq
1-\epsilon\\}\right)$
$\displaystyle\leq\sum\limits_{a=1}^{m}\mathbb{P}(\Phi_{n}(a)\leq
1-\epsilon)\leq\frac{m}{\epsilon^{2}snh_{n}^{d}},$

and

$\displaystyle\mathbb{P}\left(\max\limits_{1\leq a\leq
m}\frac{k^{*}}{\beta\Phi_{n}(a)np_{n}}\leq\frac{k^{*}}{\beta(1-\epsilon)np_{n}}\right)\geq
1-\frac{m}{\epsilon^{2}snh_{n}^{d}}.$

Since $\frac{m}{\epsilon^{2}snh_{n}^{d}}\to 0$, we have

$\displaystyle\mathbb{P}\left(\max\limits_{1\leq a,b\leq
m}(D_{22}^{-1}W_{22})_{ab}\leq\max\limits_{1\leq a\leq
m}\frac{k^{*}}{\beta\Phi_{n}(a)np_{n}}\leq M\frac{1}{nh_{n}^{d}}\right)\to
1,\quad\textnormal{as }n\to\infty,$ (11)

where $M=\frac{2k}{s\beta}>\frac{k^{*}}{(1-\epsilon)s\beta}$. Note that $M$ is
a constant independent with $n$ and $m$.

For the sake of simplicity, we say a matrix $A$ has tiny elements, if

$\displaystyle\|A\|_{\text{max}}\leq M\frac{1}{nh_{n}^{d}},$

with probability approaching 1, where $\|A\|_{\max}=\max_{ij}A_{ij}$. And
$(A)_{i}$ denotes the $i$-th row of $A$. Then $D_{22}^{-1}W_{22}$ has tiny
elements by (11). Moreover,

$\displaystyle\|(D_{22}^{-1}W_{22})^{2}\|_{\text{max}}$
$\displaystyle=\|(D_{22}^{-1}W_{22})(D_{22}^{-1}W_{22})\|_{\text{max}}$
$\displaystyle\leq(M\frac{1}{nh_{n}^{d}})^{2}m=\frac{M}{nh_{n}^{d}}(\frac{mM}{nh_{n}^{d}})$

holds with probability approaching 1. By induction,

$\displaystyle\|(D_{22}^{-1}W_{22})^{l}\|_{\text{max}}=\|(D_{22}^{-1}W_{22})(D_{22}^{-1}W_{22})^{l-1}\|_{\text{max}}\leq\frac{M}{nh_{n}^{d}}(\frac{mM}{nh_{n}^{d}})^{l-1},$

with probability approaching 1. Therefore,

$\displaystyle\|S_{l}\|_{\text{max}}=$
$\displaystyle\|D_{22}^{-1}W_{22}+\dots+(D_{22}^{-1}W_{22})^{l}\|_{\text{max}}$
$\displaystyle\leq$
$\displaystyle\|D_{22}^{-1}W_{22}\|_{\text{max}}+\dots+\|(D_{22}^{-1}W_{22})^{l}\|_{\text{max}}$
$\displaystyle\leq$
$\displaystyle\frac{M}{nh_{n}^{d}}\left(1+\dots+(\frac{mM}{nh_{n}^{d}})^{l-1}\right)\,\,\textnormal{with
probability approaching 1}.$
$\displaystyle\lim_{l\to\infty}\|S_{l}\|_{\text{max}}$
$\displaystyle\leq\lim_{l\to\infty}\frac{M}{nh_{n}^{d}}\left(1+\dots+(\frac{mM}{nh_{n}^{d}})^{l-1}\right)$
$\displaystyle\leq\frac{M}{nh_{n}^{d}}/(1-\frac{mM}{nh_{n}^{d}})\leq\frac{2M}{nh_{n}^{d}}\,\,\textnormal{with
probability approaching 1}.$

Thus
$S\stackrel{{\scriptstyle\triangle}}{{=}}\underset{l\to\infty}{\lim}S_{l}$
exists with probability approaching 1 since
$\underset{l\to\infty}{\lim}\|S_{l}\|_{\text{max}}<\infty$, and $S$ also has
tiny elements. Therefore,

$\displaystyle(D_{22}-W_{22})^{-1}=(I_{m}-D_{22}^{-1}W_{22})^{-1}D_{22}^{-1}=(I_{m}+S)D_{22}^{-1},$

with probability approaching 1.

We now go back to the solution of the hard criterion of graph-based semi-
supervised learning,

$\displaystyle\boldsymbol{\hat{f}}_{(n+1):(n+m)}$
$\displaystyle=(D_{22}-W_{22})^{-1}W_{21}\boldsymbol{Y}_{n}$
$\displaystyle=(I_{m}+S)D_{22}^{-1}W_{21}\boldsymbol{Y}_{n}=D_{22}^{-1}W_{21}\boldsymbol{Y}_{n}+SD_{22}^{-1}W_{21}\boldsymbol{Y}_{n},$
(12)

with probability approaching 1. For $1\leq a\leq m$, $\hat{f}_{(n+a)}$ equals
to the $a$th row of $(D_{22}-W_{22})^{-1}W_{21}\boldsymbol{Y}_{n}$, i.e.,

$\displaystyle\hat{f}_{(n+a)}$
$\displaystyle=\\{(D_{22}-W_{22})^{-1}W_{21}\boldsymbol{Y}_{n}\\}_{a}$ (13)
$\displaystyle=\sum\limits_{i=1}^{n}\frac{w_{i,n+a}}{d_{n+a,n+a}}Y_{i}+(S)_{a}D_{22}^{-1}W_{21}\boldsymbol{Y}_{n},$

with probability approaching 1.

By assumption, $Y_{i}$’s are bounded. Without loss of generality, assume
$\|Y_{n}\|_{\text{max}}\leq 1$. For $1\leq a\leq m$, define

$\displaystyle g_{(n+a)}=$
$\displaystyle\sum\limits_{i=1}^{n}Y_{i}\left(\frac{w_{i,n+a}}{\sum_{k=1}^{n}w_{k,n+a}}-\frac{w_{i,n+a}}{d_{n+a,n+a}}\right).$

We have

$\displaystyle 0\leq g_{(n+a)}\leq$
$\displaystyle\sum\limits_{i=1}^{n}\|Y_{n}\|_{\text{max}}\left(\frac{w_{i,n+a}}{\sum_{k=1}^{n}w_{k,n+a}}-\frac{w_{i,n+a}}{d_{n+a,n+a}}\right)$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{n}w_{i,n+a}}{\sum_{k=1}^{n}w_{k,n+a}}-\frac{\sum_{i=1}^{n}w_{i,n+a}}{\sum_{k=1}^{n+m}w_{k,n+a}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{k=n+1}^{n+m}w_{k,n+a}}{d_{n+a,n+a}}$
$\displaystyle\leq$
$\displaystyle\frac{mk}{\beta\Phi_{n}(a)np_{n}}\leq\frac{mM}{nh_{n}^{d}}\to
0,$

with probability approaching 1 as $n\to\infty$. This implies

$\displaystyle g_{(n+a)}\to 0\,\,\textnormal{in probability},$

since for any $\epsilon>0$ we can find $m,n\in\mathbb{N}$ such that
$\frac{mM}{nh_{n}^{d}}\leq\epsilon$ and

$\displaystyle\mathbb{P}(|g_{(n+a)}|\leq\epsilon)\geq\mathbb{P}\left(|g_{(n+a)}|\leq\frac{mM}{nh_{n}^{d}}\right)\to
1.$

Finally, for each $1\leq a\leq m$,

$\displaystyle\hat{f}_{(n+a)}=$
$\displaystyle\sum\limits_{i=1}^{n}\frac{w_{i,n+a}}{d_{n+a,n+a}}Y_{i}+(S)_{a}D_{22}^{-1}W_{21}\boldsymbol{Y}_{n}$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{n}\frac{w_{i,n+a}}{\sum_{k=1}^{n}w_{k,n+a}}Y_{i}+(S)_{a}D_{22}^{-1}W_{21}\boldsymbol{Y}_{n}-g_{(n+a)}.$

Since $S$ has tiny elements,

$\displaystyle\|(S)_{a}D_{22}^{-1}W_{21}\boldsymbol{Y}_{n}\|_{\text{max}}\leq\frac{mM}{nh_{n}^{d}}\to
0\,\,\textnormal{with probability approaching 1},$

which implies $(S)_{a}D_{22}^{-1}W_{21}\boldsymbol{Y}_{n}\to 0$ in
probability. The theorem then holds by the consistency of Nadaraya-Watson
estimator.

##  4 Numerical Studies

In this section, we compare the performance of the hard criterion and the soft
criterion with different tuning parameters under a linear and non-linear
model.

The inputs $X_{1},\dots X_{n+m}$ are generated independently from a truncated
multivariate normal distribution. Specifically, let $\tilde{X}_{i}$ follow a
$p$-dimensional multivariate normal with the mean $\mu=(0.5,\dots,0.5)$, and
the variance-covariance matrix

$\begin{pmatrix}0.1&0.05&0.05&\dots&0.05\\\ 0.05&0.1&0.05&\dots&0.05\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0.05&0.05&0.05&\dots&0.1\end{pmatrix}.$

We set $p=5$. For $i=1,\dots,n+m$ and $k=1,\dots,p$, let
$X_{ik}=\tilde{X}_{ik}$ if $\tilde{X}_{ik}\in[0,1]$ and $\tilde{X}_{ik}=0$
otherwise, where $X_{ik}$ and $\tilde{X}_{ik}$ are the $k$-th component of
$X_{i}$ and $\tilde{X}_{i}$, respectively.

Let $W$ be the Gaussian radial basis function (RBF) kernel, that is,

$\displaystyle
w_{ij}=\exp\left(-\frac{\|X_{i}-X_{j}\|^{2}}{\sigma^{2}}\right),\,\,\mbox{for
}1\leq i,j\leq m+n,$

where $\sigma=h_{n}=(\log n/n)^{1/5}$. Note that $W$ has compact support since
$X_{i}$’s are truncated, and the choice of $h_{n}$ satisfies the condition in
Theorem 1.

We consider two models in simulation studies. In Model 1, the responses
$Y_{i}$’s follow a logistic regression with

$\displaystyle\text{logit
}q(X_{i})=-1.35+2X_{i1}-X_{i2}+X_{i3}-X_{i4}+2X_{i5},$

for $i=1,\dots,m+n$. Model 2 uses a non-linear logit function,

$\displaystyle\text{logit
}q(X_{i})=-1.35+2X_{i1}-X_{i2}+X_{i3}-X_{i4}+2X_{i5}+X_{i1}X_{i3}+X_{i2}X_{i4},$

for $i=1,\dots,m+n$.

We compare the performance of graph-based learning methods with four different
tuning parameters, $\lambda=0,0.01,0.1$ and 5. The performance is measured by
the root mean squared error (RMSE) on the unlabeled data, that is,

$\sqrt{\frac{1}{m}\sum_{a=1}^{m}(q(X_{n+a})-\hat{q}_{n+a})^{2}}.$

Each simulation is repeated 1000 times and the average RMSEs are reported.

Figure 1 shows the RMSEs under Model 1 when the sample size of unlabeled data
$m$ is fixed as 30 and the sample size of labeled data $n=10$, 30, 50, 100,
200, 300, 500, 800, 1000 and 1500. As $n$ increases, the RMSEs of all methods
decrease as expected. More importantly, the RMSE increases as $\lambda$
increases. In particular, the hard criterion always outperforms the soft
criterion, which is consistent with our theoretical results.

Figure 2 shows the RMSEs under Model 1 when $n$ is fixed as 100 and $m=30$,
60, 100, 300, 500 and 1000. As before, the RMSE always increases as $\lambda$
increases. Moreover, the RMSEs of all methods increase as $m$ increases, which
suggests that the hard criterion may not be consistent when $m$ grows faster
than $n$. For the non-linear logit function, Figure 3 and 4 show the same
patterns as in Figure 1 and 2, respectively, which also support our
theoretical results.

##  5 Summary

In this article, we proved the consistency of graph-based semi-supervised
learning when the tuning parameter of the graph Laplacian is zero (the hard
criterion) and showed that the method can be inconsistent when the tuning
parameter is nonzero (the soft criterion). Moreover, the numerical studies
also suggest that the hard criterion outperforms the soft criterion in terms
of the RMSE. These results provide a better understanding about the
statistical properties of graph-based semi-supervised learning. Of course, the
accuracy of prediction can be measured by other indicators such as the area
under the receiver operating characteristic curve (AUC). The hard criterion
may not always be the best choice in term of these indicators. Further
theoretical properties such as rank consistency will be explored in future
research. Moreover, we would also like to investigate the behavior of these
methods when the unlabeled data grow faster than the label data.

Figure 1: Average RMSEs when $m=30$ under Model 1 Figure 2: Average RMSEs when
$n=100$ under Model 1

Figure 3: Average RMSEs when $m=30$ under Model 2 Figure 4: Average RMSEs when
$n=100$ under Model 2

## References

  * [1] S. Basu, A. Banerjee, and R. J. Mooney.  Semi-supervised clustering by seeding.  In Proceedings of the International Conference on Machine Learning, pages 19–26, 2002.
  * [2] M. Belkin, I. Matveeva, and P. Niyogi.  Regularization and semi-supervised learning on large graphs.  In Proceedings of the Seventeenth Annual Conference on Computational Learning Theory, pages 624–638, Banff, Canada, 2004.
  * [3] M. Belkin, P. Niyogi, and S. Sindhwani.  Manifold Regularization: A geometric framework for learning from labeled and unlabeled examples.  JMLR, 7:2399–2434, 2006.
  * [4] T. De Bie and N. Cristianini.  Convex methods for transduction.  In Advances in Neural Information Processing Systems, 16:73–80, 2004.
  * [5] O. Bosquet, O. Chapelle, and M. Hein.  Measure based regularization.  NIPS, 16, 2004.
  * [6] Zongwu Cai.  Weighted Nadaraya Watson regression estimation.  Statistics & Probability Letters, 51:307–318, 2001.
  * [7] O. Chapelle, B. Sch$\ddot{\text{o}}$lkopf, and A. Zien.  Semi-supervised Learning.  The MIT Press, 2006.
  * [8] Olivier Delalleau, Yoshua Bengio, and Nicolas Le Roux.  Efficient non-parametric function induction in semi-supervised learning.  In Artificial Intelligence and Statistics, 2005.
  * [9] Luc. P. Devroye.  The uniform convergence of the Nadaraya-Watson regression function estimate.  The Canadian Journal of Statistics, 6:179–191, 1978.
  * [10] Luc. P. Devroye and T. J. Wagner.  Distribution-free consistency results in nonparametric discrimination and regression function estimation.  Annals of Statistics, 8(2):231–239, 1980.
  * [11] M. Hein.  Uniform convergence of adaptive graph-based regularization.  COLT: Learning Theory, pages 50–64, 2006.
  * [12] M.D. Intriligator and Z. Griliches.  Handbook of Econometrics, volume 1.  North-Holland Publishing Company, 1988.
  * [13] Rosie Jones.  Learning to extract entitles from labeled and unlabeled text.  PhD Thesis, 2005.
  * [14] John Lafferty and Larry Wasserman.  Statistical analysis of semi-supervised regression.  NIPS, 20, 2008.
  * [15] E. A. Nadaraya.  On estimating regression.  Theor. Probability Appl, 9:141–142, 1964.
  * [16] Boaz Nadler, Nathan Srebro, and Xueyuan Zhou.  Semi-supervised learning with the Graph Laplacian: The limit of infinite unlabelled data.  NIPS, 2009.
  * [17] M. E. J. Newman.  Networks: An introduction.  Oxford University Press, 2010.
  * [18] Joel Ratsaby and Santosh S. Venkatesh.  Learning from a mixture of labeled and unlabeled examples with parametric side information.  In Proceedings of COLT ’95 Proceedings of the eighth annual conference on Computational learning theory, pages 412–417, 1995.
  * [19] Chuck Rosenberg, Martial Hebert, and Henry Schneiderman.  Semi-supervised self-training of object detection models.  In Proceedings of Seventh IEEE Workshop on Applications of Computer Vision, 2005.
  * [20] V. Vapnik.  Statistical Learning Theory.  Wiley, New York, 1998.
  * [21] G. S. Watson.  Smooth regression analysis.  Sankhy$\bar{a}$, Series A, 26:359–372, 1964.
  * [22] D. Werner.  Functional Analysis (in German).  Springer Verlag, 2005.
  * [23] Y. Zhang, M. Brady, and S. Smith.  Hidden markov random field model and segmentation of brain mr images.  IEEE Transactions on Medical Imaging, 20(1):45–57, 2001.
  * [24] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf.  Learning with local and global consistency. in S. Thrun, L. Saul, and B. Schölkopf, editors.  MIT Press, Cambridge, MA, 2004.
  * [25] X. Zhu, Zoubin Ghahramani., and John Lafferty.  Semi-supervised learning using Gaussian Fields and Harmonic Functions.  ICML, (118), 2003.
  * [26] X. Zhu and Andrew B. Goldberg.  Introduction to Semi-supervised Learning.  Morgan & Claypool Publishers, 2009.