# Complete Visibility Algorithm for Autonomous Mobile Luminous Robots under an
Asynchronous Scheduler on Grid Plane

Yonghwan Kim
Department of Computer Science
Nagoya Institute of Technology
Aichi, Japan
<EMAIL_ADDRESS>
Yoshiaki Katayama
Department of Computer Science
Nagoya Institute of Technology
Aichi, Japan
<EMAIL_ADDRESS>
Koichi Wada
Department of Applied Informatics
Hosei University
Tokyo, Japan
<EMAIL_ADDRESS>

###### Abstract

An autonomous mobile robot system is a distributed system consisting of mobile
computational entities (called robots) that autonomously and repeatedly
perform three operations: Look, Compute, and Move. Various problems related to
autonomous mobile robots, such as gathering, pattern formation, or flocking,
have been extensively studied to understand the relationship between each
robot’s capabilities and the solvability of these problems. In this study, we
focus on the complete visibility problem, which involves relocating all the
robots on an infinite grid plane such that each robot is visible to every
other robot. We assume that each robot is a luminous robot (i.e., has a light
with a constant number of colors) and opaque (not transparent). In this paper,
we propose an algorithm to achieve complete visibility when a set of robots is
given. The algorithm ensures that complete visibility is achieved even when
robots operate asynchronously and have no knowledge of the total number of
robots on the grid plane using only two colors.

_Keywords_ Autonomous Mobile Robot $\cdot$ Complete Visibility $\cdot$
Luminous Robot

##  1 Introduction

An autonomous mobile robot system is a distributed system composed of mobile
computational entities known as _robots_ which operate and move autonomously.
Each robot determines its destination based solely on the (relative) locations
of other robots obtained from its own (i.e., local) observation, and cooperate
with others to achieve a common goal for the system. The fundamental model is
proposed by Suzuki et al., wherein the robots possess no communication
abilities (_silent_), have no memory to recall past activities (_oblivious_),
and lack identifiers (_anonymous_). Furthermore, all robots are
indistinguishable from each other (_identical_) and execute the same algorithm
(_homogeneous_). Each robot continuously executes a cycle consisting of three
phases; Look, Compute and Move. In the Look phase, a robot observes the
positions of other robots. In the Compute phase, a robot caluculates its
destination using an algorithm based on the results of the last Look phase,
then proceeds to the calculated destination during the Move phase. In general,
the level of synchronization between phase executions for each robot differs,
leading to three basic schedulers: fully-synchronous ($\mathsf{FSYNC}$), semi-
synchronous ($\mathsf{SSYNC}$), and asynchronous ($\mathsf{ASYNC}$). In an
$\mathsf{FSYNC}$ scheduler model, all robots perform the cycle in a fully
synchronous manner, meaning all robots execute the same phase synchronously.
$\mathsf{SSYNC}$ is a scheduler model that allows some robots to not execute a
cycle while all robots are executing a cycle in $\mathsf{FSYNC}$.
$\mathsf{ASYNC}$ is a scheduler model that makes no assumptions about
synchronization between robots’ executions.

Several problems are considered in autonomous mobile robots systems under
various assumptions (i.e., capabilities of the robots), such as gathering
Cieliebak and Prencipe (2002), deployment Barrière et al. (2009), and pattern
formation problem Flocchini et al. (1999). The solvability of a problem is
sensitively changed by the capability of the robots; therefore, researchers
primarily aim to define the minimum capability required to solve a given
problem. Many autonomous mobile robot models neither have an explicit
communication function nor memory. However, a new model, termed the _luminous
model_ , has been introduced Luna et al. (2017). A luminous robot is equipped
with a color-changing light that can be observed by itself and/or other
robots, and can communicate with other robots and remember its own status
using its light. The luminous model clearly provides greater functionality
than the basic model. Indeed, research has demonstrated that problems
previously unsolvable using the basic model can addressed effectively with the
luminous model Luna et al. (2017); Sharma et al. (2015a). In luminous robot
systems, a primary area of interest for researchers is the number of light
colors needed to solve a problem.

Observability among robots to each other is a critical aspect in these
systems. If a robot is opaque, it can only observe its immediate neighbors
when three or more robots are align in a straight line (collinear).
Consequently, it becomes impossible to recognize the configuration of the
entire system based on personal observation alone. To address this issue, the
complete visibility problem has been studied extensively Luna et al. (2017,
2014a, 2014b); Sharma et al. (2015b, a, 2020, 2021, 2016, 2017). The complete
visibility problem is a situation where all robots are required to locate
themselves at points where they can mutually observe each other in a Euclidean
or grid plane. According to known results of this problem on a grid plane
Adhikary et al. (2018); Sharma et al. (2020, 2021), more than 10 colors of
light are required when there is no agreement on the coordinate system. As a
preliminary step in investigating the trade-off between the degree of
agreement on the coordinate system and the number of colors of lights required
to solve the problem, we propose an algorithm that addresses the problem using
only two colors of light within a system that has agreement on the orientation
and direction of grid plane’s two axes. This finding suggests that by
establishing consensus on the coordinate system, the number of required colors
can be drastically reduced.

Work | # of colors | Time Complexity | Area | Agreement | Algorithm
---|---|---|---|---|---
Adhikary et al. (2018) | 11 | finite§ | finite§ | none | deterministic
Sharma et al. (2020) | 50 |  $\mathcal{O}(D+n)$ _w.h.p._ | $\mathcal{O}(n^{2})$ | none | randomized
Sharma et al. (2020) | 17 | $\mathcal{O}(D+n)$ | $\mathcal{O}(n^{2})$ | none | deterministic†
Sharma et al. (2021) | 32 |  $\mathcal{O}(D+n)$ _w.h.p._ | $\mathcal{O}(n^{2})$ | none | randomized
This work | 2 | $\mathcal{O}((D+n))$ | $\mathcal{O}(n^{2})$ |  $X$ and $Y$ axes | deterministic
| Lower bounds of time and spatial (area) complexities
Sharma et al. (2020, 2021) | any | $\Omega(n)$ | any | any | any
Flammenkamp (1992) | any | any | $\Omega(n^{2})$ | any | any
§The complexities are not provided in Adhikary et al. (2018). It is shown in
Sharma et al. (2021) that the algorithm
in Adhikary et al. (2018) requires $\Omega(Dn+n^{2})$ time and $\Omega(n^{2})$
area.
†The algorithm operates only when the initial configuration is not symmetric.
Table 1: Comparison table between the previous works and this work and the
known lower bounds of the complexities

Related Works: The complete visibility is firstly studied by G. Di Luna et al.
Luna et al. (2014a), which shows that a set of robots with a constant-sized
color of lights (i.e., luminous model) can solve the complete visibility
problem on an Euclidean plane under $\mathsf{ASYNC}$, even there is no
assumption on the number of robots, rigidity of movements, nor chirality. They
also proposed an algorithm for oblivious robots under $\mathsf{SSYNC}$ in Luna
et al. (2014b) . Moreover, G. Di Luna et al. investigate under what conditions
luminous robots can solve the complete visibility problem, and at what cost,
in terms of the number of colors used by the robots in Luna et al. (2017).
They provided a spectrum of results which depends on the scheduler, on the
number of robots, and on the number of colors. Two algorithms, Shrink and
Contain algorithms, are introduced in Luna et al. (2017), however, the time
analyses of both algorithms are not provided. G. Sharma et al. analyzed and
proved these two algorithms: they showed that Shrink algorithm required
$\Theta$($n$) and the time complexity of Contain algorithm is
$\Omega$($n^{2}$) , where $n$ is the total number of robots, in Sharma et al.
(2015b). Furthermore, Sharma et al. proposed an improved version of Shrink
algorithm (called Modified Shrink algorithm) which decreases its time
complexity to $\mathcal{O}$($n\log n$). The optimal number of colors to solve
the complete visibility problem is discussed in Sharma et al. (2015a); this
paper presents the optimal number of colors when a scheduler is assumed as
$\mathsf{SSYNC}$ or $\mathsf{ASYNC}$, and/or robots are non-rigid or rigid. G.
Sharma et al. proposed the first algorithm for complete visibility with
$\mathcal{O}$(1) runtime under $\mathsf{SSYNC}$ in Sharma et al. (2016), and
$\mathcal{O}$($\log n$)-time complete visibility algorithm for asynchronous
robots with lights.

R. Adhikary et al. Adhikary et al. (2018) were the first to investigate the
complete visibility problem on a grid plane, introducing a deterministic and
asynchronous algorithm under the assumptions that robots do not agree on the
global coordinates nor chirality, and they do not know the total number of
robots, using 11 colors of lights. However, neither time nor spatial analysis
of the algorithm was provided in Adhikary et al. (2018) (only the finite-time
termination is stated). These complexities were later addressed in another
paper Sharma et al. (2021) after several years, which shows that the time
complexity of this algorithm is $\Omega$($Dn+n^{2}$) and the spatial
complexity 111The spatial complexity represents the area of the smallest
rectangle including all robots when the algorithm terminates (i.e., complete
visibility is achieved). is $\Omega$($n^{2}$), where $n$ is the total number
of robots and $D$ is the diameter in the initial configuration.

G. Sharma et al. proposed randomized complete visibility algorithms using 50
colors of lights in Sharma et al. (2020), and introduced another deterministic
algorithm using 17 colors of light which ensures the achievement of complete
visibility only when an initial configuration is non-symmetric. They reduced
the number of colors from 50 to 32 for the randomized algorithm in Sharma et
al. (2021). These algorithms solves the complete visibility problem in
$\mathcal{O}$($D+n$)-time and $\mathcal{O}$($n^{2}$)-space which are optimal;
the lower bounds of the time complexity and spatial complexity are also
provided in Sharma et al. (2021).

In this study, we focus on reducing the required number of colors for the
complete visibility problem on a grid plane, even under stronger assumptions.
From another perspective, we are interested in using the required number of
colors as a measure of the changes in computational power of robots under
different assumptions. As a result, we have drastically reduced the number of
colors to two, whereas all the previous works Adhikary et al. (2018); Sharma
et al. (2020, 2021) on a grid plane require more than 10 colors, if the robots
share a common sense of directions (i.e., agree on both X and Y axes). Table 1
shows the difference between the previous works Adhikary et al. (2018); Sharma
et al. (2020, 2021) and this work, where $n$ is the number of robots, $D$ is
the diameter of the initial configuration, and the known lower bounds of time
and spatial complexities. Our proposed algorithm asynchronously solves the
same problem using a smaller number of colors in optimal time and space when
$D=\mathcal{O}$($n$) provided the robots agree on two axes.

##  2 Model and Problem Definition

###  2.1 Model

Robots and Grid Plane: Let $\mathcal{R}$={$r_{1},r_{2},...,r_{n}$} be the set
of autonomous mobile robots with a total number of robots $n$. These robots
have no identifiers and cannot be distinguished from each other by appearance.
Also, robots do not have any memory to maintain their own past executions,
i.e., oblivious, and do not know the total number of robots $n$. The robots
exist on infinite grid plane $\mathcal{P}$, and every point in $\mathcal{P}$
can be occupied by at most one robot. The robots agree on the directions and
the orientations of both axes, X-axis and Y-axis, but the do not know the
origin of $\mathcal{P}$, i.e., they do not know their global coordinates. In
this paper, without loss of generality, we assume that the positive direction
of X-axis (resp. Y-axis) is _right_ (resp. _up_).

Movement of Robots: A robot can move to only one of the four grid points
adjacent to the grid point where it currently exists. Hence we assume that
every robot moves asynchronously but instantaneously: each robot cannot be
observed by any other robots while it is moving. This property is known as
_Move-Atomic_ introduced in Flocchini et al. (1999).

Lights: Each robot maintains a constant-sized visible memory register called
light that can be observed by other robots Luna et al. (2017). Each light can
be set by one among the constant number of colors. The color of the light can
be changed at the end of Compute in the LCM cycle (will be described later) if
necessary. In other words, the robot decides where to move and the color of
the light based on the observation results, and starts moving after changing
the color of the light. In the proposed algorithm, we assume that a robot uses
only two colors, $\mathscr{A}$ and $\mathscr{B}$,
$\mathcal{C}\in\\{\mathscr{A},\mathscr{B}\\}$.

Visibility Range and Transparency: We assume that there is no limit to the
robot’s field of view, i.e., a robot has unlimited visibility range. Each
robot is not transparent, i.e., opaque; if robot $r_{k}$ exists on the line
between two robots $r_{i}$ and $r_{j}$, then robots $r_{i}$ and $r_{j}$ cannot
observe each other.

Operations and Scheduler: Each robot performs one of the four operations:
Look, Compute, Move, and Wait. Let Look, Compute, Move be one cycle (called
LCM cycle). (Wait) A robot is in a standby state. A robot which is in Wait
should perform its LCM operations again within the finite time. At the start,
all robots are in the Wait state. (Look) A robot gets the color of its own
light. A robot gets the coordinates and light color of the other robots in its
local coordinate system which is self-centric, i.e., the origin is the
position of the robot itself. As a result of Look, a robot gets a set
$\mathcal{V}_{r}=\\{r_{0},r_{1},\cdots,r_{M}\\}$ of the coordinates and light
colors of the observed robots based on its local coordinate system. (Compute)
A robot executes an algorithm to determine the color of its light and the
destination point. As the result of the executing algorithm, a robot
immediately changes the color of its light (if necessary). (Move) A robot
instantaneously moves to the destination point determined by Compute
operation.

We consider an asynchronous scheduler ($\mathsf{ASYNC}$) which has no
assumption on the timing of each robot’s operation. This means that all robots
perform their operations at unpredictable time instants and durations.

Configuration: Let configuration $C_{t}$ be the set of the (global)
coordinates and colors of all robots at a given time $t$:
$C_{t}=\\{(r_{1.x}^{t},r_{1.y}^{t},r_{1.\mathcal{C}}^{t}),(r_{2.x}^{t},r_{2.y}^{t},r_{2.\mathcal{C}}^{t}),\cdots$
$(r_{n.x}^{t},r_{n.y}^{t},r_{n.\mathcal{C}}^{t})\\}$, where $r_{i.x}^{t}$
(resp. $r_{i.y}^{t}$) is the x-coordinate (y-coordinate) of robot $r_{i}$ on
grid $\mathcal{P}$, and $r_{i.\mathcal{C}}^{t}$ is the color of $r_{i}$’s
light at time $t$. Remind that no robot knows its global coordinate.

Configuration $C_{t}$ is changed into another configuration $C_{t+1}$ when at
least one of the robots moves or changes the color of its light. In other
words, under an $\mathsf{ASYNC}$ scheduler, configuration $C_{t+1}$ is
obtained by any atomic operation of any robot’s operates Compute or Move at
configuration $C_{t}$ (if it moves or changes its color).

###  2.2 Complete Visibility Problem

Here we define the complete visibility problem as the following.

###### Definition 1

The Complete Visibility Problem. Given a set of robots which is initially
located on the distinct points in grid plane. Algorithm $\mathcal{A}$ solves
the complete visibility problem if $\mathcal{A}$ satisfies all the following
conditions: (1) Algorithm $\mathcal{A}$ eventually terminates; algorithm
$\mathcal{A}$ eventually reaches a configuration such that no robot can move,
and (2) Every robot can observe all other robots, i.e., any three robots are
not collinear, when algorithm $\mathcal{A}$ terminates.

##  3 Proposed Algorithm

###  3.1 Basic Strategy

In this subsection, we briefly give the basic strategy of the proposed
algorithm for solving the complete visibility problem under $\mathsf{ASYNC}$.
To achieve complete visibility, we refer to the previous study Roth (1951):
for any prime number $m$, it is known that any three distinct points
$(i^{2}\bmod m,i)$, for any distinct $i\leq m$, are not collinear. Therefore,
we aim to make a configuration such that all robots are located on
$(i^{2}\bmod m,i)$ for distinct $i$ and $n\leq m$, where $n$ is the total
number of robots and $m$ is the smallest prime number which is equal to or
greater than $n$. The proposed algorithm to solve the complete visibility
problem consists of the following three phases.

  1. 1.

Line Formation Phase: The first phase of the proposed algorithm locates all
robots on a straight line parallel to the Y-axis.

  2. 2.

Coordinate System Generation Phase: In the second phase, the algorithm
determines three reference points by moving three robots to generate the
agreed coordinate system, because the robots do not agree on the global
coordinate system, and no robot knows its global coordinates. All robots can
recognize the current common coordinate system by referring these reference
points. Moreover, the robots which moves to the reference points can count the
total number of robots $n$, and this information $n$ is (implicitly)
propagated to all other robots by their positions.

  3. 3.

Complete Visibility Achievement Phase: Each robot computes its destination
point on the common coordinate system generated in the previous phase, and
moves to its appropriate position to achieve complete visibility.

The proposed algorithm consists of 26 rules based on the observation result of
each robot; 15 rules for the first phase, 8 rules of the second one, and 3
rules for the last phase. Because of the lack of space, the detailed algorithm
is presented in Appendix.

###  3.2 Presentation of Algorithm

Before the introduction of the proposed algorithm, we present some notations
and functions which are used in the presentation of the proposed algorithm.

We present the proposed algorithm using the conditions and action, which means
each robot executes the action when all conditions are satisfied, and
represent as $<$Conditions$>$ $\to$ $<$Action$>$. In $<$Conditions$>$, we use
a triplet (ordered triple) $(\mathsf{X},\mathsf{Y},\mathsf{C})$, which means
that the number of robots satisfying the following three conditions among all
observed robots: $\mathsf{X}$ (resp. $\mathsf{Y}$) indicates the range of
x-coordinate (resp. y-coordinate), and $\mathsf{C}$ indicates the color of the
light: $\mathsf{C}\in\mathcal{C}\cup\\{\mathbb{*}\\}$, where $\mathbb{*}$
means any color (i.e., do not care). $<$Action$>$ is presented as a tuple
$(a^{d},\mathcal{C})$: the former one $a^{d}$ represents the destination point
to move and the latter one $\mathcal{C}$ represents the color of the light to
change. Remind that each robot can move to its adjacent (four) point, thus we
can present the destination point using $a^{d}$, where $a\in\\{x,y\\}$ and
$d\in\\{+,-\\}$, which means the orientation and the direction respectively
based on its local coordination system. Both $a^{d}$ and $\mathcal{C}$ can
have $\bot$, which means null movement (does not move) and keep color (does
not change color) respectively. We also use a macro $\mathsf{my}\mathcal{C}$
which indicates its own light. As a common rule that applies to all rules, a
robot never moves if the destination point is already occupied by another
robot, even if the conditions are satisfied.

Here we give an example of the algorithm to help to understand.

Algorithm 1 An example of Algorithm

Rule $x$: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(3\geq x\geq
1,y=2,\mathscr{A})=3\land(x=0,y\geq 1,\mathbb{*})=1\to(x^{+},\mathscr{B})$

Algorithm 1 shows the $x$-th rule: robot $r_{i}$ changes the color of its
light to $\mathscr{B}$ (in the end of its Compute phase) and moves to the
positive direction of X-axis (in its Move phase) if all the following
conditions are satisfied; (1) the color of its light is $\mathscr{A}$, (2) the
number of the observed robots, whose x-coordinate is between 1 and 3 (based on
$r_{i}$’s local coordination), y-coordinate is exactly 2 (based on $r_{i}$’s
local coordination), and color of the light is $\mathscr{B}$, is equal to 3,
and (3) there exists a robot on the positive direction of $r_{i}$’s current
Y-axis.

It is worthwhile to mention that different algorithms are required where the
number of robots $n$ is 2, 3, and 4 or more. We present the algorithm only for
$n\geq 4$, which is the most general case. Note that the number of robots can
be counted in the coordinate system generation phase, thus we can determine
the algorithm to execute based on $n$.

###  3.3 Phase 1: The Line Formation Phase

Algorithm 2 shows the first phase of the proposed algorithm, called _the Line
Formation Phase_ , which consists of 15 rules, from Rule 1 to Rule 15.

Algorithm 2 The Line Formation Phase

/* From an initial configuration to configuration $C_{A}$ */

Rule 1: $\mathsf{my}\mathcal{C}=\mathscr{A}\ \land\
(x\leq-1,y\leq-1,\mathbb{*})=0\ \land\ (x\geq 1,y\leq-1,\mathbb{*})=0\land\
(x=0,y\leq-1,\mathbb{*})=0\ \land\ (x\geq 1,y=0,\mathbb{*})=0\land\
(x\leq-1,y=0,\mathscr{A})=1\ \land\ (-\infty\leq x\leq\infty,-\infty\leq
y\leq\infty,\mathscr{B})=0\to(y^{-},\bot)$

Rule 2:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x\leq-1,y\leq-1,\mathbb{*})=0\land(x\geq
1,y\leq-1,\mathbb{*})=0\land(x=0,y\leq-1,\mathbb{*})=0\land(x\geq
1,y=0,\mathbb{*})=0\land(x\leq-1,y=0,\mathbb{*})=0\land((x=0,y\geq
1,\mathscr{A})\geq 1\lor(x\geq 1,y\geq 1,\mathscr{A})\geq 1)\land(-\infty\leq
x\leq\infty,-\infty\leq y\leq\infty,\mathscr{B})=0\to(x^{+},\bot)$

Rule 3: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x\leq-1,y\geq
1,\mathscr{A})\geq 1\land(\lnot(x\leq-1),\lnot(y\geq
1),\mathbb{*})=0\to(\bot,\mathscr{B})$

/* From configuration $C_{A}$ to configuration $C_{B}$ */

Rule 4: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x\leq
1,y\leq-1,\mathscr{B})=1\land(\lnot(x\geq
1),\lnot(y\leq-1),\mathscr{B})=0\to(x^{+},\bot)$

Rule 5:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=1,y\leq-1,\mathscr{B})=1\land(\lnot(x=1),\lnot(y\leq-1),\mathscr{B})=0\land(-\infty\leq
x\leq\infty,y\leq-1,\mathscr{A})=0\to(x^{+},\bot)$

Rule 6:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=0,y\leq-1,\mathscr{B})=1\land(-\infty\leq
x\leq\infty,\lnot(y\leq-1),\mathscr{B})=0\land(-\infty\leq
x\leq\infty,y\leq-1,\mathscr{A})=0\land(x\geq 0,y\geq
0,\mathscr{A})=0\to(\bot,\mathscr{B})$

/* From configuration $C_{B}$ to configuration $C_{C}$ */

Rule 7: $\mathsf{my}\mathcal{C}=\mathscr{B}\land(x\geq 1,-\infty\leq
y\leq\infty,\mathbb{*})=0\land(x=0,y\geq 1,\mathbb{*})=0\land(x\leq-1,y\geq
0,\mathscr{A})\geq 1\to(y^{+},\bot)$

Rule 8: $\mathsf{my}\mathcal{C}=\mathscr{B}\land(x\geq 1,-\infty\leq
y\leq\infty,\mathbb{*})=0\land(x=0,y\leq-1,\mathbb{*})=0\land(x\leq-1,y\leq
0,\mathscr{A})\geq 1\to(y^{-},\bot)$

Rule 9: $\mathsf{my}\mathcal{C}=\mathscr{A}\land 1\leq(x\geq 2,-\infty\leq
y\leq\infty,\mathscr{B})\leq 2\land(x\leq 1,-\infty\leq
y\leq\infty,\mathscr{B})=0\to(x^{+},\bot)$

Rule 10: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=1,y\geq
1,\mathscr{B})=1\land(x=1,y\leq-1,\mathscr{B})=1\land(x\leq 0,-\infty\leq
y\leq\infty,\mathscr{B})=0\to(x^{+},\bot)$

Rule 11: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=1,y\geq
1,\mathscr{B})=1\land(x=1,y\leq-1,\mathscr{B})=1\land(x\leq 0,-\infty\leq
y\leq\infty,\mathscr{B})=0\land(x=1,y=0,\mathscr{A})=1\land(x\leq 0,y\geq
1,\mathbb{*})=0\to(y^{+},\bot)$

Rule 12: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=1,y\geq
1,\mathscr{B})=1\land(x=1,y\leq-1,\mathscr{B})=1\land(x\leq 0,-\infty\leq
y\leq\infty,\mathscr{B})=0\land(x=1,y=0,\mathscr{A})=1\land(x\leq
0,y\leq-1,\mathbb{*})=0\to(y^{-},\bot)$

Rule 13: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=1,y\geq
1,\mathscr{B})=1\land(x=1,y\leq-1,\mathscr{B})=1\land(x\leq 0,-\infty\leq
y\leq\infty,\mathscr{B})=0\land(x=1,y=0,\mathscr{A})=1\land(x\leq
0,y\leq-1,\mathbb{*})=0\land(x\leq 0,y\geq 1,\mathbb{*})=0\to(y^{+},\bot)$

/* From configuration $C_{C}$ to configuration $C_{D}$ */

Rule 14:$(x=0,y\geq 2,\mathbb{*})=1\land(x\geq 1,-\infty\leq
y\leq\infty,\mathbb{*})=0\land(x\leq-1,-\infty\leq
y\leq\infty,\mathbb{*})=0\to(y^{+},\bot)$

Rule 15:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=0,y=1,\mathscr{B})=1\land(x\geq
1,-\infty\leq y\leq\infty,\mathbb{*})=0\land(x\leq-1,-\infty\leq
y\leq\infty,\mathbb{*})=0\to(\bot,\mathscr{B})$

In this phase, we consider four different configurations, called
configurations from $C_{A}$ to $C_{D}$ respectively, as the following.

Configuration $C_{A}$: Only one robot with color $\mathscr{B}$ is located at a
point with the smallest y-coordinate and the largest x-coordinate and all
other robots have lights with color $\mathscr{A}$.

Configuration $C_{B}$: Two robots with color $\mathscr{B}$ are on the same
Y-axis and can observe each other (i.e., there is no other robot between the
two robots). Moreover, all other robots than the two robots with color
$\mathscr{B}$ have lights with color $\mathscr{A}$. The two robots with color
$\mathscr{B}$ are located on the same or smaller y-coordinate than any other
robots with color $\mathscr{A}$.

Configuration $C_{C}$: All robots are located on the same Y-axis, and the
robot with the smallest y-coordinate and the robot with the largest
y-coordinate have lights with color $\mathscr{B}$, while all other robots have
lights with color $\mathscr{A}$.

Configuration $C_{D}$: All robots are located on the same Y-axis, have the
same lights with color $\mathscr{B}$, and are lined up without gaps.

(a) $C_{A}$ (b) $C_{B}$

(c) $C_{C}$ (d) $C_{D}$

Figure 1: Examples of configurations from $C_{A}$ to $C_{D}$

Figure 1(a) to Figure 1(d) illustrate the examples of these four
configurations in the Line Formation Phase respectively. First of all, the
proposed algorithm determines the reference point to form a straight line from
any initial configuration so that all the robots have light with color
$\mathscr{A}$. The proposed algorithm uses the robot which has the largest
x-coordinate and the smallest y-coordinate, i.e., the rightmost and undermost
robot, as the reference point to determine where the robots are lined up.

The proposed algorithm uses 3 rules to achieve configuration $C_{A}$ from any
initial configuration (refer to Rules 1 to 3 in Algorithm 2). In any initial
configuration, there exists a robot that cannot observe any other robots in
the third and forth quadrants based on its local coordinate system by assuming
its current position as the origin, i.e., there is no robot located on the
point with the smaller y-coordinate than the robot’s. If the robot cannot
observe any other robots in positive direction of the same X-axis neither, the
robot becomes the reference robot (denoted by $\alpha$). And robot $\alpha$
moves to the appropriate reference point. If robot $\alpha$ can observe
another robot in its negative direction of the same X-axis, it first moves to
the negative direction along the current Y-axis (Figure 2(a)). If robot
$\alpha$ cannot observe any other robots on the negative direction of its
current X-axis, robot $\alpha$ moves to the positive direction along the
X-axis (Figure 2(b)). If robot $\alpha$ cannot observe any other robots both
in the negative direction of its current X-axis and in its first quadrant, it
changes its color of the light to $\mathscr{B}$, because the robot reaches the
reference point (Figure 2(c)). This implies that robot $\alpha$ changes its
color from $\mathscr{A}$ to $\mathscr{B}$ only when it observes all other
robots with color $\mathscr{B}$ in its second quadrant. When robot $\alpha$
changes its color to $\mathscr{B}$, configuration $C_{A}$ is achieved.

(a) Rule 1 (b) Rule 2

(c) Rule 3

Figure 2: Examples of movements by Rules 1 to 3

The proposed algorithm uses 3 rules to achieve configuration $C_{B}$ from
configuration $C_{A}$ (refer to Rules 4 to 6 in Algorithm 2). Let $y_{0}$ be
the Y-axis where robot $\alpha$ exists in configuration $C_{A}$, and each
$y_{i}$ be the Y-axis $i$ away from $y_{0}$ on the positive or negative
direction of X-axis. For example, $y_{1}$ represents the Y-axis whose
x-coordinate is 1 larger than $y_{0}$, i.e., the right neighbor of $y_{0}$,
$y_{-1}$ represents the Y-axis whose x-coordinate is 1 smaller than $y_{0}$,
i.e., the left neighbor of $y_{0}$. In configuration $C_{A}$, robots with
color $\mathscr{A}$ can observe only one robot with color $\mathscr{B}$ in its
forth quadrant, or no robot with color $\mathscr{B}$ (because they are not
transparent). The robot with color $\mathscr{A}$, which observes a robot with
color $\mathscr{B}$ in its forth quadrant, moves to the positive direction of
its current X-axis toward $y_{-1}$ (Figure 3(a)). Note that each robot moves
only to the positive direction of X-axis i.e., right, and a robot does not
move to its destination point if another robot exists there to avoid a
collision. Therefore, each robot with color $\mathscr{B}$ stops when it
reaches $y_{-1}$ or there exists another robot on its adjacent point on the
positive direction of X-axis (if it can observe robot $\alpha$).

Now we consider a robot with color $\mathscr{A}$ which reaches $y_{-1}$ and
cannot observe any other robot on its negative side of Y-axis. We call this
robot $\beta$ and only robot $\beta$ moves to $y_{0}$ whereas all other robots
with color $\mathscr{A}$ stops when they reaches $y_{-1}$. After that, robot
$\beta$ changes its light color to $\mathscr{B}$ (Figure 3(c)). When robot
$\beta$ changes the light color to $\mathscr{B}$, configuration $C_{B}$ is
achieved.

(a) Rule 4 (b) Rule 5

(c) Rule 6

Figure 3: Examples of movements by Rules 4 to 6

The proposed algorithm uses 7 rules to achieve configuration $C_{C}$ from
configuration $C_{B}$ (refer to Rules 7 to 13 in Algorithm 2). In
configuration $C_{B}$, two robots with color $\mathscr{B}$ (robots $\alpha$
and $\beta$) exist on the same Y-axis and they can observe each other. Robot
$\alpha$ has a smaller y-coordinate than all the other robots, and robot
$\beta$ has a equal or smaller y-coordinate than all the other robots except
robot $\alpha$. Note that, robots $\alpha$ and $\beta$ have larger
x-coordinate than all other robots. Our strategy in this phase is to locate
all other robots than $\alpha$ and $\beta$ at the points between two robots
$\alpha$ and $\beta$. To use this strategy, robots $\alpha$ and $\beta$ should
move away from each other if necessary. Notice that, in Configuration $B$,
only two robots $\alpha$ and $\beta$ have a light with color $\mathscr{B}$ and
all other robots are located on the negative side of X-axis in local
coordinates of robots $\alpha$ and $\beta$ (Figure 4(a)). If a robot with
color $\mathscr{A}$ observes one or two robots with color $\mathscr{B}$ on its
positive side of X-axis, it moves along its current X-axis toward the $y_{-1}$
(Figure 4(b)). If a robot on $y_{-1}$ observes one robot with color
$\mathscr{B}$ in the first quadrant and another robot with color $\mathscr{B}$
in forth quadrant, it moves to its neighboring point on $y_{0}$ (Figure 4(c))
if the point is empty. However, if there is another robot on its neighboring
point in $y_{0}$, it moves along its Y-axis according to the following rules:
if there is no robot in the positive (resp. negative) direction of its current
Y-axis and the second (resp. third) quadrant based on its local coordinate
system, the robot moves to the positive (resp. negative) direction of its
Y-axis (Figure 4(d)). Note that if it is possible to move to both directions,
the robot moves to the positive direction of Y-axis due to the priority of the
algorithm. When all robots are located on $y_{0}$, the configuration satisfies
configuration $C_{C}$.

(a) Rules 7 and 8 (b) Rule 9

(c) Rule 10 (d) Rules 11 to 13

Figure 4: Examples of movements by Rules 7 to 13

The proposed algorithm uses two rules to achieve configuration $C_{D}$ from
configuration $C_{C}$ (refer to Rule 14 and Rule 15 in Algorithm 2). In
configuration $C_{C}$, all robots are located on the same Y-axis, and only two
robots with the smallest and largest y-coordinate respectively (robots
$\alpha$ and $\beta$) have light with color $\mathscr{B}$, while all the other
robots have light with color $\mathscr{A}$. Note that, in this case, all
robots observe no robot in all quadrants and on its current X-axis. If a robot
observes an other robot in the positive direction of its Y-axis but no robot
on its neighboring point in the positive direction of its Y-axis, the robot
moves to the positive direction of its Y-axis to close the gap (Figure 6(a)).
If a robot with color $\mathscr{A}$ observes in the adjacent point in the
positive direction of the Y-axis, it changes its color into $\mathscr{B}$
(Figure 6(b)). If all robots are lined up without gaps, configuration $C_{D}$
is achieved, and the first phase, The Line Formation Phase, is completed.

(a) Rule 14 (b) Rule 15

Figure 5: Examples of movement by Rules 14 and 15

Figure 6: $C_{E}$ when $n=9$

###  3.4 Phase 2: The Coordinate System Generation Phase

Algorithm 3 presents the second phase of the proposed algorithm, called _the
Coordinate System Generation Phase_ , which consists of 8 rules, from Rule 16
to Rule 23.

Algorithm 3 Coordinate System Generation Phase

/* From configuration $C_{D}$ to configuration $C_{E}$ */

Rule 16:
$\mathsf{my}\mathcal{C}=\mathscr{B}\land(x=0,y=1,\mathscr{B})=1\land(\lnot(x=0,y=1),\mathbb{*})=0\to(x^{-},\bot)$

Rule 17:
$\mathsf{my}\mathcal{C}=\mathscr{B}\land(x=-1,y\leq-1,\mathscr{B})=1\land(-\infty\leq
x\leq\infty,y=0,\mathbb{*})=0\to(\bot,\mathscr{A})$

Rule 18: $\mathsf{my}\mathcal{C}=\mathscr{B}\land(x=1,y\geq 1,\mathscr{A})\geq
3\land(\lnot(x=1,y\geq 1),\mathbb{*})=0\to(x^{-},\bot)$

Rule 19:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=-2,y=-1,\mathscr{B})=1\land(x=0,y=1,\mathscr{A})=1\land(\lnot((x=-2,y=-1)\land(x=0,y=1)),\mathbb{*})=0\to(x^{-},\bot)$

Rule 20:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=-1,y=-1,\mathscr{B})=1\land(x=1,y\geq
1,\mathscr{A})\geq 2\land(\lnot((x=-1,y=-1)\land(x=1,y\geq
1)),\mathbb{*})=0\to(\bot,\mathscr{B})$

Rule 21:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=-1,y\leq-1,\mathscr{B})=1\land(x=-2,y\leq-1,\mathscr{B})=1\land(x=0,y=-1,\mathscr{A})=1\land(\lnot((x=-1,y\leq-1)\land(x=-2,y\leq-1)\land(x=0,y=-1)),\mathbb{*})=0\to(x^{-},\bot)$

Rule 22:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=0,y\leq-1,\mathscr{B})=1\land(x=-1,y\leq-1,\mathscr{B})=1\land(x=0,y=-m+1,\mathscr{B})=0\land(\lnot(x=0,y\leq-1)\land(x=-1,y\leq-1),\mathscr{B})=0\to(y^{+},\bot)$

Rule 23:
$\mathsf{my}\mathcal{C}=\mathscr{A}\land(x=0,y\leq-1,\mathscr{B})=1\land(x=-1,y\leq-1,\mathscr{B})=1\land(x=0,y=-m+1,\mathscr{B})=1\land(\lnot(x=0,y\leq-1)\land(x=-1,y\leq-1),\mathscr{B})=0\to(\bot,\mathscr{B})$

Here we define configuration $C_{E}$ which is the goal configuration of this
phase as the following:

Configuration $C_{E}$: Let a robot with color $\mathscr{B}$ with the smallest
y-coordinate be the origin, there exists two robots with color $\mathscr{B}$
at (1,1) and (1,$m$-1) respectively, where $m$ is the smallest prime number
greater than or equal to $n$. All other robots have light with color
$\mathscr{A}$ and are lined up with no gaps on the line, $y=2$, from (2,2) to
(2,$n$-2) (Figure 6).

In this phase, only some specific robots can operate (moves or changes the
color of light) in every configuration, thus the goal configuration is
achieved by the sequential operations of the robots. The proposed algorithm
uses 8 rules to achieve the second phase (refer to Algorithm 3).

(a) Rule 16 (b) Rule 17

(c) Rule 18 (d) Rule 19

Figure 7: Examples of movements by Rules 16 to 19

Remind that in configuration $C_{D}$, which is the final configuration of the
first phase, all robots with color $\mathscr{B}$ are lined up with no gaps.
Therefore, there exists only one robot (robot $\alpha$) which cannot observe
any other robot in the negative direction of Y-axis, and robot $\alpha$ moves
to the negative direction of X-axis by Rule 16 (Figure 7(a)). By this
movement, all other robots can observe a robot with $\mathscr{B}$ in their
third quadrant, and the robots changes their colors into $\mathscr{A}$ by Rule
17 (Figure 7(b)). If robot $\alpha$ observes no robot with color
$\mathscr{B}$, it moves again to the negative direction of X-axis by Rule 18
(Figure 7(c)). After that, the robot with the smallest y-coordinate among the
robots with color $\mathscr{A}$ moves to the negative direction of X-axis by
Rule 19 (Figure 7(a)), and changes its color into $\mathscr{B}$ by Rule 20
(Figure 8(a)). The robot with the largest y-coordinate (robot $\beta$) moves
to the negative direction of X-axis by Rule 21 (Figure 8(b)). It is worthwhile
to mention that robot $\beta$ can observe both robots with color $\mathscr{B}$
because the number of the robots $n$ is greater than 3. Furthermore, robot
$\beta$ can observe all other robots after the execution of Rule 21, this
means that robot $\beta$ can count the number of robots $n$ even it moves to
the positive direction of Y-axis. Robot $\beta$ can repeatedly move to the
positive direction of Y-axis until it reaches (1,$m$-1) (assuming that robot
$\alpha$ is on the origin) by Rule 22 (Figure 8(c)). When robot $\beta$
reaches (1,$m$-1), it changes the color of its light into $\mathscr{B}$ by
Rule 23 (Figure 8(d)). As a result, the configuration satisfies configuration
$C_{E}$, and the second phase is completed.

(a) Rule 20 (b) Rule 21

(c) Rule 22 (d) Rule 23

Figure 8: Examples of movements by Rules 20 to 23

###  3.5 Phase 3: The Complete Visibility Achievement Phase

Algorithm 4 shows the third phase of the proposed algorithm, called _the
Complete Visibility Achievement Phase_ , which consists of 3 rules, from Rule
24 to Rule 26.

Algorithm 4 Complete Visibility Achievement Phase

/* From configuration $C_{E}$ to configuration $C_{F}$ */

Rule24: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x\leq-1,y\geq
1,\mathscr{B})\geq 1\land(x\leq-1,y\leq-1,\mathscr{B})\geq
1\land(x\leq-1,-\infty\leq
y\leq\infty,\mathscr{A})=0\land\mathtt{LookCS()}=1\land\mathtt{MyLocation()}\neq(\Upsilon^{2}\bmod
m,\Upsilon)\to(x^{+},\bot)$

Rule25: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x\leq-1,y\geq
1,\mathscr{B})\geq 1\land(x\leq-1,y\leq-1,\mathscr{B})\geq
1\land(x\leq-1,-\infty\leq
y\leq\infty,\mathscr{A})=0\land\mathtt{LookCS()}=0\to(x^{+},\bot)$

Rule26: $\mathsf{my}\mathcal{C}=\mathscr{A}\land(x\leq-1,y\geq
1,\mathscr{B})\geq 1\land(x\leq-1,y\leq-1,\mathscr{B})\geq
1\land(x\leq-1,-\infty\leq
y\leq\infty,\mathscr{A})=0\land\mathtt{LookCS()}=1\land\mathtt{MyLocation()}=(\Upsilon^{2}\bmod
m,\Upsilon)\to(\bot,\mathscr{B})$

We define the final configuration $C_{F}$ as the following. Note that the
complete visibility problem is solved when configuration $C_{F}$ is achieved
because any three robots in $C_{F}$ are not collinear.

Configuration $C_{F}$: Let a robot with color $\mathscr{B}$ with the smallest
y-coordinate be the origin, all robots have light with color $\mathscr{B}$ and
are located at ($i^{2}\bmod m,i$) for distinct $i$ ($i\in\mathbb{N}_{0}$),
where $m$ is the smallest prime number greater than or equal to the number of
robots $n$.

As the result of the second phase, Complete Visibility Achievement Phase, the
coordinate system is defined by the three robots with color $\mathscr{B}$,
which are located at (0,0), (1,1), and (1,$m$-1) respectively assuming that
the point occupied by the robot with the smallest y-coordinate (robot
$\alpha$) is the origin. All other robots than the three reference robots can
observes robots both in the second and third quadrants only during the third
phase. In Phase 3, we use two functions, $\mathtt{LookCS()}$ and
$\mathtt{MyLocation()}$: $\mathtt{LookCS()}$ returns 1 if a robot can observe
all three reference robots with color $\mathscr{B}$, and
$\mathtt{MyLocation()}$ returns its current coordinate based on the generated
coordinate system by the three reference robots. Note that all robots have
distinct y-coordinates since the end of the first phase thus we use each
robot’s y-coordinate as distinct $i\in\mathbb{N}_{0}$. In the proposed
algorithm, $\Upsilon$ represents the robot’s y-coordinate based on the
generated coordinate system (it is obvious that each robot knows $\Upsilon$
only when $\mathtt{LookCS()}=1$).

Figure 9: Example of $C_{F}$

Figure 10: Problem by obstruction

The main strategy of this phase is that each robot with color $\mathscr{A}$
repeatedly moves to the positive direction of X-axis until it reaches
($\Upsilon^{2}\bmod m$,$\Upsilon$) where $\Upsilon$ is its y-coordinate based
on the defined coordinate system, and changes its color into $\mathscr{B}$
when it reaches ($\Upsilon^{2}\bmod m$,$\Upsilon$). Hence, when all robots
change their color into $\mathscr{B}$, the complete visibility is achieved,
i.e., configuration $C_{F}$ is achieved (refer to Figure 10).

However, every robot with color $\mathscr{B}$ moves asynchronously, there can
be exist a robot cannot observe some reference robots caused by the
obstruction by the other robots (Figure 10). Therefore, we consider the
pseudo-synchronous movement of the robots with color $\mathscr{A}$: each robot
with color $\mathscr{A}$ can move only when no other robot with color
$\mathscr{A}$ exists in the negative side of X-axis. This implies that each
robot with color $\mathscr{A}$ has to wait until all other robots with color
$\mathscr{A}$ reach the point on the same Y-axis. The proposed algorithm uses
3 rules to achieve the third phase (refer to Algorithm 4).

Basically, each robot with color $\mathscr{A}$ checks whether its current
position is ($\Upsilon^{2}\bmod m$,$\Upsilon$) or not: if it is located on
($\Upsilon^{2}\bmod m$,$\Upsilon$), it changes its color into $\mathscr{B}$
and stops by Rule 26 (Figure 11(c)), otherwise it moves to the positive
direction of X-axis unless there exist a robot with color $\mathscr{A}$ on the
negative side of X-axis by Rule 24 (Figure 11(a)). If a robot with color
$\mathscr{A}$ cannot observe the three reference robots, it moves to the
positive direction of X-axis without regard to its current position by Rule 25
(Figure 11(b)): this is because that if the robot is located on
($\Upsilon^{2}\bmod m$,$\Upsilon$), it can observe all the reference robots.

(a) Rule 24 (b) Rule 25

(c) Rule 26

Figure 11: Examples of movement by Rules 24 to 26

###  3.6 Analysis of the Algorithm

###### Theorem 1

The proposed algorithm guarantees to solve the complete visibility problem
using only two colors, $\mathcal{C}=\\{\mathscr{A},\mathscr{B}\\}$, under an
asynchronous scheduler in $\mathcal{O}(D+n)$ asynchronous rounds and within
$\mathcal{O}(n^{2})$ area when an arbitrary set of robots with color
$\mathscr{A}$ is given.

We omit the proof of the correctness of the proposed algorithm, but here we
briefly give a proof sketch of the time complexity of the proposed algorithm.
We analyze the time complexity using an asynchronous round that is defined as
the shortest sequence of an execution where each robot performs its three
operations at least once.

The worst case of Phase 1 is a configuration so that all robots except two
robots, $\alpha$ and $\beta$, are lined up along X-axis: only one robot may
move in the first round after this configuration under an adversary scheduler
because all robots located on $y_{i}$ (where $i\leq-2$) cannot move even they
are activated by the scheduler. However, two robots can move in the next round
regardless of the sequence of activation, as the same manner, $i$ robots can
move in the $i$-th round. the head (leading) robot may stop only one round to
wait until robot $\beta$ moves, which causes all robots to stop once: this
implies that the tail robot may stop at most $\mathcal{O}(n)$ rounds. As a
result, from any initial configuration, all robots are lined up along X-axis
in $\mathcal{O}(D)$ rounds (where $D$ is the diameter of the initial
configuration), the robot farthest away from the target line, $y_{0}$, begins
to move after $\mathcal{O}(n)$ rounds, and it moves $\mathcal{O}(n)$ times but
it may wait at most $\mathcal{O}(n)$ times. Hence, Phase 1 requires
$\mathcal{O}(D+n)$ rounds.

In Phase 2, two robots (other than robot $\beta$) among the three reference
robots move the constant number of rounds and one robot (robot $\beta$) moves
$\mathcal{O}(m)$ times. Thus Phase 2 converges in $\mathcal{O}(n)$ rounds by
_Bertrand’s postulate_ ; for any integer $n>3$, there always exists at least
one prime number $p$ with $n<p<2n-2$.

In Phase 3, every robot which is not located on the goal position can move to
the positive direction of X-axis in every round, at most $\mathcal{O}(m)$
times. As the same reason of Phase 2, Phase 3 also converges in
$\mathcal{O}(n)$ rounds. Hence the proposed algorithm terminates in
$\mathcal{O}(D+n)+\mathcal{O}(n)+\mathcal{O}(n)=\mathcal{O}(D+n)$ rounds.

It is obvious that the spatial complexity of the proposed algorithm is
$\mathcal{O}(n^{2})$ due to the deployment strategy: $(i^{2}\bmod m,i)$ for
distinct $i<n$ (note that $n<m$).

##  4 Conclusion

In this paper, we consider the complete visibility problem which is a problem
to relocate all robots on grid plane to observe each other, i.e., no three
robots are collinear. We proposed an (asynchronous) algorithm for oblivious
robots to solve the complete visibility problem in $\mathcal{O}(D+n)$
asynchronous rounds under the following assumptions: the robots (1) agree on
both axes, X-axis and Y-axis, but do not agree on the position of the origin,
(2) have unlimited visibility range, (3) are not transparent, (4) do not know
the number of robots, and (5) have the light with only 2 colors.

Compared with the previous studies, the proposed algorithm uses the fewest
number of colors to achieve complete visibility, even we assume the stronger
geometrical agreement. In many previous works for the luminous model, i.e.,
robots with lights, the necessary number of colors is one of the important
issue. As the main contribution of this work, we show that the necessary
number of colors to solve the complete visibility problem on grid plane can
reduce to 2 if robots have the common sense of direction, i.e., they agree on
the both axes.

As a future work, we consider the weaker assumptions of the geometrical
agreement, e.g., only one axis or chirality. To clarify the possibility of the
algorithm by the robots without light, i.e., fully oblivious robots, is
another future work: to propose an algorithm or to provide the impossibility
result.

## Acknowledgements

This work was supported in part by JSPS KAKENHI Grant Numbers 19K11823,
20K11685, 20KK0232, and 21K11748.

## References

  * Cieliebak and Prencipe [2002] Mark Cieliebak and Giuseppe Prencipe.  Gathering autonomous mobile robots.  In _Proc. of the 9th International Colloquium on Structural Information and Communication Complexity_ , volume 13 of _Proceedings in Informatics_ , pages 57–72. Carleton Scientific, 2002.
  * Barrière et al. [2009] Lali Barrière, Paola Flocchini, Eduardo Mesa Barrameda, and Nicola Santoro.  Uniform scattering of autonomous mobile robots in a grid.  In _23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS_ , pages 1–8, 2009.
  * Flocchini et al. [1999] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer.  Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots.  In _Algorithms and Computation, 10th Int. Symposium, ISAAC_ , volume 1741 of _Lecture Notes in Computer Science_ , pages 93–102, 1999.  doi:10.1007/3-540-46632-0_10.  URL https://doi.org/10.1007/3-540-46632-0_10.
  * Luna et al. [2017] Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Federico Poloni, Nicola Santoro, and Giovanni Viglietta.  Mutual visibility by luminous robots without collisions.  _Inf. Comput._ , 254:392–418, 2017.
  * Sharma et al. [2015a] Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay.  Mutual visibility with an optimal number of colors.  In _11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS_ , volume 9536 of _LNCS_ , pages 196–210, 2015a.
  * Luna et al. [2014a] Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Nicola Santoro, and Giovanni Viglietta.  Robots with lights: Overcoming obstructed visibility without colliding.  In _Stabilization, Safety, and Security of Distributed Systems SSS_ , volume 8756 of _LNCS_ , pages 150–164, 2014a.
  * Luna et al. [2014b] Giuseppe Antonio Di Luna, Paola Flocchini, Federico Poloni, Nicola Santoro, and Giovanni Viglietta.  The mutual visibility problem for oblivious robots.  In _Proc. of the 26th Canadian Conference on Computational Geometry, CCCG_ , 2014b.
  * Sharma et al. [2015b] Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay.  Bounds on mutual visibility algorithms.  In _Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG_ , 2015b.
  * Sharma et al. [2020] Gokarna Sharma, Ramachandran Vaidyanathan, and Jerry L. Trahan.  Optimal randomized complete visibility on a grid for asynchronous robots with lights.  In _2020 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW_ , pages 607–616, 2020.
  * Sharma et al. [2021] Gokarna Sharma, Ramachandran Vaidyanathan, and Jerry L. Trahan.  Optimal randomized complete visibility on a grid for asynchronous robots with lights.  _Int. J. Netw. Comput._ , 11(1):50–77, 2021.
  * Sharma et al. [2016] Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan, Costas Busch, and Suresh Rai.  Complete visibility for robots with lights in O(1) time.  In _Stabilization, Safety, and Security of Distributed Systems SSS_ , volume 10083 of _LNCS_ , pages 327–345, 2016.
  * Sharma et al. [2017] Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan, Costas Busch, and Suresh Rai.  O(log n)-time complete visibility for asynchronous robots with lights.  In _2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS_ , pages 513–522, 2017.
  * Adhikary et al. [2018] Ranendu Adhikary, Kaustav Bose, Manash Kumar Kundu, and Buddhadeb Sau.  Mutual visibility by asynchronous robots on infinite grid.  In _14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS_ , volume 11410 of _LNCS_ , pages 83–101, 2018.
  * Flammenkamp [1992] Achim Flammenkamp.  Progress in the no-three-in-line-problem.  _J. Comb. Theory, Ser. A_ , 60(2):305–311, 1992\.
  * Roth [1951] K. F. Roth.  On a problem of heilbronn.  _Journal of The London Mathematical Society-second Series_ , pages 198–204, 1951.


# Asymptotic Gaussian Fluctuations of Eigenvectors in Spectral Clustering

Hugo Lebeau, Florent Chatelain, Romain Couillet H. Lebeau and R. Couillet are
with Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38 000 Grenoble,
France, (e-mail: {hugo.lebeau, romain.couillet}@univ-grenoble-alpes.fr).F.
Chatelain is with Univ. Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, 38 000
Grenoble, France (e-mail: florent.chatelain@grenoble-inp.fr).

###### Abstract

The performance of spectral clustering relies on the fluctuations of the
entries of the eigenvectors of a similarity matrix, which has been left
uncharacterized until now. In this letter, it is shown that the signal $+$
noise structure of a general spike random matrix model is transferred to the
eigenvectors of the corresponding Gram kernel matrix and the fluctuations of
their entries are Gaussian in the large-dimensional regime. This CLT-like
result was the last missing piece to precisely predict the classification
performance of spectral clustering. The proposed proof is very general and
relies solely on the rotational invariance of the noise. Numerical experiments
on synthetic and real data illustrate the universality of this phenomenon.

###### Index Terms:

Spectral clustering, central limit theorem, kernel matrix, spike eigenvector,
Gaussian fluctuations.

##  I Introduction

Spectral clustering is a popular unsupervised classification technique which
finds applications in many domains, such as image segmentation [1], text
mining [2], and as a general purpose method for data analysis [3, 4, 5]. It
relies on the spectrum of a suitably chosen similarity matrix to perform
dimensionality reduction before applying a standard clustering algorithm such
as $K$-means. Consider, e.g., the following toy example where $n$ vectors
${\bm{x}}_{1},\ldots,{\bm{x}}_{n}\in{\mathbb{R}}^{p}$ are separated in two
clusters ${\mathcal{C}}^{+}$, ${\mathcal{C}}^{-}$ centered around
$\pm{\bm{\mu}}$, i.e., ${\bm{x}}_{i}=\pm{\bm{\mu}}+{\bm{w}}_{i}$ where
${\bm{w}}_{i}\sim{\mathcal{N}}({\mathbf{0}},{\bm{I}}_{n})$. Then, the dominant
eigenvector $\hat{{\bm{v}}}$ of the Gram kernel matrix
${\bm{K}}=\frac{1}{p}[{\bm{x}}_{i}^{\top}{\bm{x}}_{j}]_{1\leqslant
i,j\leqslant n}$ is an information-theoretically optimal estimator [6] of the
vector $\frac{1}{\sqrt{n}}{\bm{j}}$ such that $j_{i}=\pm 1$ if
${\bm{x}}_{i}\in{\mathcal{C}}^{\pm}$. In this case, clustering is achieved
with the trivial decision rule ${\bm{x}}_{i}\to{\mathcal{C}}^{\pm}$ if
$\hat{v}_{i}\gtrless 0$.

The achievable performances of spectral clustering can be theoretically
predicted thanks to the study of random matrix models corresponding to
similarity matrices. For this purpose, random matrix theory offers powerful
tools [7, 8, 9]. In particular, it allows to derive the limiting spectral
distribution of the kernel matrix and to predict to the position of isolated
eigenvalues in _spiked_ random matrix models [10, 11, 12]. The latter are of
particular importance as, in a wide range of problems, the information of
interest can be modeled as a low-rank signal corrupted with noise. In our
previous toy example, the data matrix
${\bm{X}}=\begin{bmatrix}{\bm{x}}_{1}&\ldots&{\bm{x}}_{n}\end{bmatrix}$ is a
rank-one perturbation ${\bm{\mu}}{\bm{j}}^{\top}$ of a noise matrix ${\bm{W}}$
with i.i.d. ${\mathcal{N}}(0,1)$ entries. In order to theoretically predict
the error rate of spectral clustering for a given signal-to-noise ratio, one
must therefore study the behavior of the dominant eigenvectors of the
similarity matrix. Tools such as the ones used in [12, 13] allow to express
the quality of their alignment with the true underlying signal, i.e.,
$\frac{1}{\sqrt{n}}\lvert{\bm{j}}^{\top}\hat{{\bm{v}}}\rvert$. Although this
tells us when an estimation of the signal is possible (depending on the
signal-to-noise ratio) and its efficiency, a precise characterization of the
fluctuations of the entries of spiked eigenvectors still lacks to rigorously
predict the error rate of spectral clustering. Indeed, in our toy example, the
expected error rate ${\mathbb{P}}(\hat{v}_{i}j_{i}<0)$ cannot be expressed
unless the law of $\hat{{\bm{v}}}$ is known.

Yet, it is often stated that the entries of $\hat{{\bm{v}}}$ have Gaussian
fluctuations in the large-dimensional regime, so that
${\mathbb{P}}(\hat{v}_{i}j_{i}<0)$ is a Gaussian integral. In [14], this
result is formally stated but no proof is given. Hence, we fill this missing
gap with a rigorous proof of this phenomenon for a general spiked random
matrix model. The proposed proof is not restricted to Gaussian noise (in fact,
the noise only needs to be rotationally invariant) and can easily be adapted
to most standard spiked models, although we stick to a standard signal $+$
noise model here. The demonstration can be summarized in two simple facts  1.
an eigenvector of the kernel matrix can be decomposed into the sum of a
deterministic signal part and a random noise part  2. the random part is
uniformly distributed on a certain sphere, hence any finite subset of its
entries tends to a centered Gaussian vector in the large-dimensional limit.

In this letter, we consider a general signal $+$ noise random matrix model and
briefly recall known results regarding its limiting spectral distribution and
the behavior of its dominant eigenvalues and eigenvectors. Then, we show that
the entries of the kernel eigenvectors indeed have Gaussian fluctuations in
the large-dimensional regime. We present a short, self-contained and general
proof which is our main contribution. Finally, we illustrate this result with
numerical experiments on synthetic and real data.

Simulations. Python codes to reproduce simulations are available in the
following GitHub repository
https://github.com/HugoLebeau/asymptotic_fluctuations_spectral_clustering.

##  II Model and Main Result

###  II-A Notations

$a$, ${\bm{a}}$ and ${\bm{A}}$ respectively denote a scalar, a vector and a
matrix. $a_{i}$ and $A_{i,j}$ are their entries. The set of positive integers
below $n$ is $[n]=\\{1,\ldots,n\\}$. The cardinality of a set ${\mathcal{E}}$
is $\lvert{\mathcal{E}}\rvert$. Given an ordered set of indices
${\mathcal{I}}=(i_{1},\ldots,i_{\lvert{\mathcal{I}}\rvert})$,
$[{\bm{a}}]_{\mathcal{I}}$ is the vector
$\begin{bmatrix}a_{i_{1}}&\ldots&a_{i_{\lvert{\mathcal{I}}\rvert}}\end{bmatrix}^{\top}$.
The norm of a vector ${\bm{x}}\in{\mathbb{R}}^{n}$ is
$\lVert{\bm{x}}\rVert=\sqrt{{\bm{x}}^{\top}{\bm{x}}}$. The unit sphere in
${\mathbb{R}}^{n}$ is
${\mathbb{S}}^{n-1}=\\{{\bm{x}}\in{\mathbb{R}}^{n}\mid\lVert{\bm{x}}\rVert=1\\}$.
${\bm{I}}_{n}$ is the $n\times n$ identity matrix. For a real number
$x\in{\mathbb{R}}$, $[x]^{+}=\max(0,x)$ and $\delta_{x}$ is the Dirac measure
at $x$. $X\sim{\mathcal{L}}$ states that the random variable $X$ is
distributed according to the law ${\mathcal{L}}$. The convergence in
distribution of a sequence of random variables $(X_{n})_{n\geqslant 0}$ to
${\mathcal{L}}$ is denoted
$X_{n}\xrightarrow[n\to+\infty]{{\mathcal{D}}}{\mathcal{L}}$. Its almost sure
convergence to $L$ is denoted $X_{n}\xrightarrow[n\to+\infty]{\text{a.s.}}L$.
${\mathcal{N}}({\bm{\mu}},{\bm{\Sigma}})$ is the multivariate normal
distribution with mean ${\bm{\mu}}$ and covariance ${\bm{\Sigma}}$. The set of
eigenvalues of a square matrix ${\bm{A}}$ is its spectrum,
$\operatorname{Sp}{\bm{A}}$. Given two real-valued sequences
$(u_{n})_{n\geqslant 0}$ and $(v_{n})_{n\geqslant 0}$, we write
$u_{n}=\operatorname*{\mathcal{O}}(v_{n})$ if $\lvert u_{n}/v_{n}\rvert$ is
bounded as $n\to+\infty$ and $u_{n}\asymp v_{n}$ if $u_{n}/v_{n}\to 1$.

###  II-B Spiked Matrix Model

Consider the following statistical model

${\bm{X}}={\bm{P}}+{\bm{W}}~{}\in{\mathbb{R}}^{p\times
n},\quad{\bm{P}}={\bm{L}}{\bm{V}}^{\top}$ (1)

with ${\bm{L}}\in{\mathbb{R}}^{p\times K}$ and
${\bm{V}}=\begin{bmatrix}{\bm{v}}_{1}&\dots&{\bm{v}}_{K}\end{bmatrix}\in{\mathbb{R}}^{n\times
K}$ such that ${\bm{V}}^{\top}{\bm{V}}={\bm{I}}_{K}$. It models a _low-rank_
signal ${\bm{P}}$ corrupted by additive Gaussian noise
$W_{i,j}\overset{\text{i.i.d.}}{\sim}{\mathcal{N}}(0,1)$. In a spectral
clustering perspective, $K$ is the number of classes and
${\bm{P}}={\bm{M}}{\bm{J}}^{\top}$ where
${\bm{M}}=\begin{bmatrix}{\bm{\mu}}_{1}&\dots&{\bm{\mu}}_{K}\end{bmatrix}$
gathers the $K$ cluster centroids in dimension $p$ and $J_{i,k}=1$ if
${\bm{x}}_{i}$ is in the $k$-th cluster, i.e.,
${\bm{x}}_{i}={\bm{\mu}}_{k}+{\bm{w}}_{i}$, and $0$ otherwise. This is
congruent with model (1): define the $K\times K$ diagonal matrix ${\bm{D}}$
such that $D_{k,k}=n_{k}$ where $n_{k}$ is the number of samples belonging to
the $k$-th cluster, then ${\bm{L}}={\bm{M}}{\bm{D}}^{1/2}$ and
${\bm{V}}={\bm{J}}{\bm{D}}^{-1/2}$.

Given model (1), we are interested in the reconstruction of ${\bm{V}}$ from
the dominant eigenvectors of the Gram kernel matrix
${\bm{K}}=\frac{1}{p}{\bm{X}}^{\top}{\bm{X}}$. We study this problem in the
asymptotic regime where $p,n\to+\infty$ at the same rate, i.e.,
$0<c\overset{\text{def}}{=}\lim p/n<+\infty$. This models the fact that, in
practice, the number of samples $n$ is comparable to the number of features
$p$ and they are both large. Moreover, we make the following assumptions.

######  Assumption 1.

All classes are of comparable size, i.e., $\liminf n_{k}/n>0$ as
$p,n\to+\infty$ for all $k\in[K]$.

######  Assumption 2.

$\displaystyle\lim_{p,n\to+\infty}\max_{\begin{subarray}{c}1\leqslant
i\leqslant n\\\ 1\leqslant k\leqslant K\end{subarray}}\sqrt{n}V_{i,k}^{2}=0$.

######  Assumption 3.

The eigenvalues $\ell_{1}\geqslant\ldots\geqslant\ell_{K}>0$ of
$\frac{1}{n}{\bm{L}}^{\top}{\bm{L}}$ are not degenerate (i.e., have
multiplicity one) and the columns of ${\bm{V}}$ are ordered accordingly.

Assumption 3 is only to simplify the presentation of the results so it is not
necessary, but often verified in practice. However, Assumption 2 states that
${\bm{V}}$ must be _delocalized_ , i.e., not sparse. It is naturally verified
for spectral clustering as a result of Assumption 1 since
${\bm{V}}={\bm{J}}{\bm{D}}^{-1/2}$, but the results presented below concern
the statistical model (1), which is more general and also encompasses PCA for
example [13].

###  II-C Eigenvalue Distribution and Spiked Eigenvalues

We briefly recall known results on model (1) in order to set the ground for
our main result in Theorem 3.

The first theorem concerns the limiting behavior of the empirical spectral
distribution of ${\bm{K}}$, that is
$\frac{1}{n}\sum_{\lambda\in\operatorname{Sp}{\bm{K}}}\delta_{\lambda}$.

######  Theorem 1 (Marčenko-Pastur distribution [15, 7, 8, 9]).

${\bm{K}}$ has a limiting spectral distribution
$\mu_{\text{MP}}=[1-c]^{+}\delta_{0}+\nu$ with

${\mathrm{d}}\nu(x)=\frac{\sqrt{[x-E_{-}]^{+}[E_{+}-x]^{+}}}{2\pi
c^{-1}x}{\mathrm{d}}x,\quad E_{\pm}=(1\pm\sqrt{c^{-1}})^{2}.$

In other words, as $p,n\to+\infty$, the histogram of eigenvalues of ${\bm{K}}$
converges weakly to $\mu_{\text{MP}}$, as depicted in Figure 1.

Figure 1: Empirical Spectral Distribution (ESD) and Limiting Spectral
Distribution (LSD) of ${\bm{K}}=\frac{1}{p}{\bm{X}}^{\top}{\bm{X}}$ predicted
by Theorem 1. The green dashed lines are the positions $\xi_{k}$ of isolated
eigenvalues predicted by Theorem 2. Experimental setting: $n=1000$, $p=2000$,
$K=3$, $(n_{1},n_{2},n_{3})=(333,334,333)$,
$(\lVert{\bm{\mu}}_{1}\rVert,\lVert{\bm{\mu}}_{2}\rVert,\lVert{\bm{\mu}}_{3}\rVert)=(3,4,5)$.

The second theorem specifies the limiting behavior of the $K$ dominant
eigenvalues and eigenvectors of ${\bm{K}}$. It can be found as a particular
case of [13, Theorem 2].

######  Theorem 2.

Let $(\lambda_{k},\hat{{\bm{v}}}_{k})_{k\in[K]}$ denote the dominant
eigenvalue-eigenvector pairs of ${\bm{K}}$ such that
$\lambda_{1}\geqslant\ldots\geqslant\lambda_{K}$. Define the following two
functions,

$\displaystyle F(t)$ $\displaystyle=t^{4}+2t^{3}+\left(1-c\right)t^{2}-2ct-c,$
$\displaystyle G(t)$
$\displaystyle=1+\frac{1+t}{c}+\frac{1}{1+t}+\frac{1}{t\left(1+t\right)}$

and $\Gamma\in{\mathbb{R}}$, the largest real root of $F$. Then, for all
$k\in[K]$,

$\displaystyle\lambda_{k}$
$\displaystyle\xrightarrow[p,n\to+\infty]{\text{a.s.}}\xi_{k}\overset{\text{def}}{=}\left\\{\begin{array}[]{ll}G(\ell_{k})&\text{if}~{}\ell_{k}\geqslant\Gamma\\\
G(\Gamma)=E_{+}&\text{otherwise}\end{array}\right.,$
$\displaystyle\left\lvert{\bm{v}}_{k}^{\top}\hat{{\bm{v}}}_{k}\right\rvert^{2}$
$\displaystyle\xrightarrow[p,n\to+\infty]{\text{a.s.}}\zeta_{k}\overset{\text{def}}{=}\left\\{\begin{array}[]{ll}\frac{F(\ell_{k})}{\ell_{k}\left(1+\ell_{k}\right)^{3}}&\text{if}~{}\ell_{k}\geqslant\Gamma\\\
0&\text{otherwise}\end{array}\right..$

Due to the low-rank perturbation ${\bm{P}}$, the $K$ dominant eigenvalues of
${\bm{K}}$ may isolate themselves from the bulk characterized in Theorem 1 if
their corresponding signal-to-noise ratios (the eigenvalues of
$\frac{1}{n}{\bm{L}}^{\top}{\bm{L}}$) are large enough. This is a well-known
BBP-type phase transition phenomenon [16]. Theorem 2 specifies this behavior
by stating that $\lambda_{k}$ leaves the bulk if, and only if,
$\ell_{k}\geqslant\Gamma$ and further gives its almost sure asymptotic
position $G(\ell_{k})$. This is illustrated in Figure 1. Moreover, Theorem 2
indicates the almost sure asymptotic alignment $\zeta_{k}$ of the
corresponding eigenvector $\hat{{\bm{v}}}_{k}$ with the underlying signal
${\bm{v}}_{k}$. This is depicted in Figure 2 (top row).

Figure 2: Dominant eigenvectors of
${\bm{K}}=\frac{1}{p}{\bm{X}}^{\top}{\bm{X}}$. Top: Coordinates of
$\hat{{\bm{v}}}_{k}$ (blue) and the underlying signal
$\sqrt{\zeta_{k}}{\bm{v}}_{k}$ (orange) with $\zeta_{k}$ given in Theorem 2.
The dotted orange lines are the $\pm 1\sigma$-error curves deduced from
Theorem 3. Bottom: Histogram of the entries of
$\hat{{\bm{v}}}_{k}-\sqrt{\zeta_{k}}{\bm{v}}_{k}$ (blue) and probability
density function of ${\mathcal{N}}(0,\frac{1-\zeta_{k}}{n})$ (orange).
Experimental setting: like in Figure 1.

It should be noted that the previous results are not restricted to Gaussian
noise: up to a control on the moments of the distribution, they can be
generalized thanks to an “interpolation trick” [17, Corollary 3.1]. In
addition, a similar spectral behavior is observed with non-i.i.d. noise
following the realistic assumption that it is _concentrated_ [18, 19].

###  II-D Fluctuations of Spiked Eigenvectors Entries

The convergence of $\lvert{\bm{v}}_{k}^{\top}\hat{{\bm{v}}}_{k}\rvert^{2}$ to
$\zeta_{k}$ stated in Theorem 2 is an important result which justifies the use
of the dominant eigenvectors of ${\bm{K}}$ as estimators of the underlying
signal ${\bm{V}}$. Yet, it is not enough to characterize its reconstruction
performance. Indeed, the fluctuations of the entries of $\hat{{\bm{v}}}_{k}$
must be known to fully characterize _how_ it is aligned with ${\bm{v}}_{k}$.

Consider, e.g., the multi-class spectral clustering problem with
${\bm{P}}={\bm{M}}{\bm{J}}^{\top}$. Here,
$[{\bm{v}}_{k}]_{i}=J_{i,k}/\sqrt{n_{k}}$. Hence, ${\bm{x}}_{i}$ is classified
in the $k$-th class if
$[\hat{{\bm{v}}}_{k}]_{i}>[\hat{{\bm{v}}}_{k^{\prime}}]_{i}$ for all
$k^{\prime}\neq k$. The reconstruction performance thus depends on the
probability of correct classification
${\mathbb{P}}([\hat{{\bm{v}}}_{k}]_{i}>[\hat{{\bm{v}}}_{k^{\prime}}]_{i}\mid
J_{i,k}=1)$. In the theorem below, we show that the entries of
$\hat{{\bm{v}}}_{k}$ asymptotically have Gaussian fluctuations around those of
${\bm{v}}_{k}$ with variance $(1-\zeta_{k})/n$, as illustrated in the bottom
row of Figure 2.

######  Theorem 3.

For all finite ordered set of indices
${\mathcal{I}}=(i_{1},\ldots,i_{\lvert{\mathcal{I}}\rvert})\subset[n]$ and
$k\in[K]$,

$\frac{\sqrt{n}\left[\hat{{\bm{v}}}_{k}-\sqrt{\zeta_{k}}{\bm{v}}_{k}\right]_{\mathcal{I}}}{\sqrt{1-\zeta_{k}}}\xrightarrow[p,n\to+\infty]{{\mathcal{D}}}{\mathcal{N}}({\mathbf{0}},{\bm{I}}_{\left\lvert{\mathcal{I}}\right\rvert})$

with $\hat{{\bm{v}}}_{k}$ such that
${\bm{v}}_{k}^{\top}\hat{{\bm{v}}}_{k}\geqslant 0$ (otherwise, consider
$-\hat{{\bm{v}}}_{k}$).

This result invokes the quantity $\zeta_{k}$ introduced in Theorem 2, which
quantifies the alignment of $\hat{{\bm{v}}}_{k}$ with ${\bm{v}}_{k}$. Theorem
3 specifies that $[{\bm{v}}_{k}]_{\mathcal{I}}$ behaves like
${\mathcal{N}}(\sqrt{\zeta_{k}}[{\bm{v}}_{k}]_{\mathcal{I}},\frac{1-\zeta_{k}}{n})$
in the large-dimensional regime. That is, the more $\hat{{\bm{v}}}_{k}$ is
aligned with ${\bm{v}}_{k}$ (i.e., the closer $\zeta_{k}$ is to $1$), the more
it concentrates around $\sqrt{\zeta_{k}}{\bm{v}}_{k}$, since the variance is
$(1-\zeta_{k})/n$. Furthermore, the entries of
$[\hat{{\bm{v}}}_{k}]_{\mathcal{I}}$ are _asymptotically independent_ for any
_finite_ ordered set of indices ${\mathcal{I}}$. In the multi-class spectral
clustering problem considered above, since $\hat{{\bm{v}}}_{k}$ and
$\hat{{\bm{v}}}_{k^{\prime}}$ are asymptotically independent if
$k^{\prime}\neq k$ [20], Theorem 3 allows to express

${\mathbb{P}}([\hat{{\bm{v}}}_{k}]_{i}>[\hat{{\bm{v}}}_{k^{\prime}}]_{i}\mid
J_{i,k}=1)\asymp\Phi\left(\sqrt{\frac{n}{n_{k}}\frac{\zeta_{k}}{2-(\zeta_{k}+\zeta_{k^{\prime}})}}\right)$

where
$\Phi:x\mapsto\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{t^{2}}{2}}{\mathrm{d}}t$
is the Gaussian cumulative distribution function.

We prove Theorem 3 in Section III below. The proof hinges on the rotational
invariance of the noise (Lemma 1). In fact, it does not need the entries of
${\bm{W}}$ to be distributed according to the Gaussian law, but only that its
distribution be invariant under isometries. This makes it a very general
proof, which can easily be adapted to most standard spiked models as those
discussed, e.g., in [9, §2.5.4].

##  III Proof of Main Result

Consider the tangent-normal decomposition

$\hat{{\bm{v}}}_{k}=\sum_{\kappa=1}^{K}\tau_{\kappa}{\bm{v}}_{\kappa}+\sqrt{1-\left\lVert{\bm{\tau}}\right\rVert^{2}}\,\hat{{\bm{v}}}_{k}^{\sharp}$
(2)

where
$\hat{{\bm{v}}}_{k}^{\sharp}=({\bm{I}}_{n}-{\bm{V}}{\bm{V}}^{\top})\frac{\hat{{\bm{v}}}_{k}}{\sqrt{1-\lVert{\bm{\tau}}\rVert^{2}}}$
is a unit-norm vector orthogonal to the span of ${\bm{V}}$ and
${\bm{\tau}}=\begin{bmatrix}\tau_{1}&\ldots&\tau_{K}\end{bmatrix}^{\top}$ with
$\tau_{\kappa}={\bm{v}}_{\kappa}^{\top}\hat{{\bm{v}}}_{k}$ measuring the
cosine between ${\bm{v}}_{\kappa}$ and $\hat{{\bm{v}}}_{k}$. Let ${\bm{O}}$ be
an $n\times n$ orthogonal matrix such that ${\bm{O}}{\bm{V}}={\bm{V}}$ — i.e.,
a rotational symmetry about the span of ${\bm{V}}$ — and
$\tilde{{\bm{K}}}\overset{\text{def}}{=}{\bm{O}}{\bm{K}}{\bm{O}}^{\top}$.
Then,

$\tilde{{\bm{K}}}=\frac{1}{p}\left(\left[{\bm{O}}{\bm{V}}\right]{\bm{L}}^{\top}{\bm{L}}\left[{\bm{O}}{\bm{V}}\right]^{\top}+\left[{\bm{O}}{\bm{V}}\right]{\bm{L}}^{\top}\left[{\bm{W}}{\bm{O}}^{\top}\right]\right.\\\
\left.+\left[{\bm{W}}{\bm{O}}^{\top}\right]^{\top}{\bm{L}}\left[{\bm{O}}{\bm{V}}\right]^{\top}+\left[{\bm{W}}{\bm{O}}^{\top}\right]^{\top}\left[{\bm{W}}{\bm{O}}^{\top}\right]\right).$

######  Lemma 1.

${\bm{W}}$ and ${\bm{W}}{\bm{O}}^{\top}$ are identically distributed.

###### Proof.

The distribution of
$[{\bm{W}}{\bm{O}}^{\top}]_{i,j}=\sum_{k=1}^{n}W_{i,k}O_{j,k}$ is
${\mathcal{N}}(0,1)$ and
$\operatorname{Cov}([{\bm{W}}{\bm{O}}^{\top}]_{i,j},[{\bm{W}}{\bm{O}}^{\top}]_{i^{\prime},j^{\prime}})$
is $1$ if $(i,j)=(i^{\prime},j^{\prime})$ and $0$ otherwise. Hence
$[{\bm{W}}{\bm{O}}^{\top}]_{i,j}\overset{\text{i.i.d.}}{\sim}{\mathcal{N}}(0,1)$.
∎

According to the previous lemma, $\tilde{{\bm{K}}}$ follows the same model as
${\bm{K}}$ since ${\bm{O}}{\bm{V}}={\bm{V}}$. Therefore, its $k$-th dominant
eigenvector can likewise be decomposed as

$\tilde{{\bm{v}}}_{k}=\sum_{\kappa=1}^{K}\tilde{\tau}_{\kappa}{\bm{v}}_{\kappa}+\sqrt{1-\left\lVert\tilde{{\bm{\tau}}}\right\rVert^{2}}\,\tilde{{\bm{v}}}_{k}^{\sharp}$

with $\tilde{\tau}_{\kappa}={\bm{v}}_{\kappa}^{\top}\tilde{{\bm{v}}}_{k}$ and
$\tilde{{\bm{v}}}_{k}^{\sharp}=({\bm{I}}_{n}-{\bm{V}}{\bm{V}}^{\top})\frac{\tilde{{\bm{v}}}_{k}}{\sqrt{1-\lVert\tilde{{\bm{\tau}}}\rVert^{2}}}$
_identically distributed to $\hat{{\bm{v}}}_{k}^{\sharp}$_. Yet,
$\tilde{{\bm{v}}}_{k}={\bm{O}}\hat{{\bm{v}}}_{k}$. Thus,
$\hat{{\bm{v}}}_{k}^{\sharp}$ and ${\bm{O}}\hat{{\bm{v}}}_{k}^{\sharp}$ are
identically distributed for all $n\times n$ orthogonal matrix ${\bm{O}}$ such
that ${\bm{O}}{\bm{V}}={\bm{V}}$. Consequently, $\hat{{\bm{v}}}_{k}^{\sharp}$
is uniformly distributed on ${\mathbb{S}}^{n-1}\cap{\bm{V}}^{\perp}$, where
${\bm{V}}^{\perp}=\\{{\bm{w}}\in{\mathbb{R}}^{n}\mid{\bm{V}}^{\top}{\bm{w}}={\mathbf{0}}\\}$.

Then, $\hat{{\bm{v}}}_{k}^{\sharp}$ can be written as ${\bm{U}}{\bm{u}}$ where
${\bm{u}}$ is uniformly distributed on
${\mathbb{S}}^{n-1-K}\subset{\mathbb{R}}^{n-K}$ and
${\bm{U}}\in{\mathbb{R}}^{n\times(n-K)}$ is such that
${\bm{U}}^{\top}{\bm{U}}={\bm{I}}_{n-K}$ and
${\bm{U}}^{\top}{\bm{V}}={\mathbf{0}}$ (the columns of ${\bm{U}}$ form an
orthonormal basis of ${\bm{V}}^{\perp}$ in ${\mathbb{R}}^{n}$). We use the
following theorem to identify the asymptotic distribution of
$\sqrt{n}[\hat{{\bm{v}}}_{k}^{\sharp}]_{\mathcal{I}}$.

######  Theorem 4 ([21, 22]).

The characteristic function of a vector ${\bm{w}}$ uniformly distributed on
${\mathbb{S}}^{n-1}$ is given by
$\varphi_{\bm{w}}({\bm{t}})\overset{\text{def}}{=}\mathbb{E}[e^{{\mathrm{i}}{\bm{t}}^{\top}{\bm{w}}}]=\Omega_{n}(\lVert{\bm{t}}\rVert)$
with

$\Omega_{n}:r\geqslant
0\mapsto\frac{\Gamma(\frac{n}{2})}{\sqrt{\pi}\Gamma(\frac{n-1}{2})}\int_{-1}^{1}e^{{\mathrm{i}}rt}\left(1-t^{2}\right)^{\frac{n-3}{2}}~{}{\mathrm{d}}t.$

Moreover, we have the following pointwise convergence,

$\lim_{n\to+\infty}\Omega_{n}(r\sqrt{n})=e^{-\frac{r^{2}}{2}}.$

Let ${\bm{t}}\in{\mathbb{R}}^{n}$ be such that $t_{i}=0$ if
$i\not\in{\mathcal{I}}$. The characteristic function of
$\sqrt{n}[\hat{{\bm{v}}}_{k}^{\sharp}]_{\mathcal{I}}$ is

$\displaystyle\varphi_{\sqrt{n}[\hat{{\bm{v}}}_{k}^{\sharp}]_{\mathcal{I}}}(t_{i_{1}},\ldots,t_{i_{\left\lvert{\mathcal{I}}\right\rvert}})$
$\displaystyle=\mathbb{E}\left[e^{{\mathrm{i}}\sqrt{n}{\bm{t}}^{\top}{\bm{U}}{\bm{u}}}\right]$
$\displaystyle=\Omega_{n-K}(\sqrt{n}\left\lVert{\bm{U}}^{\top}{\bm{t}}\right\rVert)$

and
$\lVert{\bm{U}}^{\top}{\bm{t}}\rVert=\sqrt{\lVert{\bm{t}}\rVert^{2}-\lVert{\bm{V}}^{\top}{\bm{t}}\rVert^{2}}=\lVert{\bm{t}}\rVert+\operatorname*{\mathcal{O}}(\lVert{\bm{V}}^{\top}{\bm{t}}\rVert^{2})$.
According to Assumption 2, $\sqrt{n}\lVert{\bm{V}}^{\top}{\bm{t}}\rVert^{2}\to
0$ as $p,n\to+\infty$, thus, following Theorem 4,

$\varphi_{\sqrt{n}[\hat{{\bm{v}}}_{k}^{\sharp}]_{\mathcal{I}}}(t_{i_{1}},\ldots,t_{i_{\left\lvert{\mathcal{I}}\right\rvert}})\xrightarrow[p,n\to+\infty]{}e^{-\frac{\left\lVert{\bm{t}}\right\rVert^{2}}{2}}.$

Therefore, by Lévy’s continuity theorem [23], we can conclude that
$\sqrt{n}[\hat{{\bm{v}}}_{k}^{\sharp}]_{\mathcal{I}}\xrightarrow{{\mathcal{D}}}{\mathcal{N}}({\mathbf{0}},{\bm{I}}_{\left\lvert{\mathcal{I}}\right\rvert})$
as $p,n\to+\infty$. And, finally, given decomposition (2), Theorem 2 and the
independence of $\hat{{\bm{v}}}_{k}$ and $\hat{{\bm{v}}}_{k^{\prime}}$ if
$k^{\prime}\neq k$ [20],

$\hat{{\bm{v}}}_{k}=\sqrt{\zeta_{k}}{\bm{v}}_{k}+\sqrt{1-\zeta_{k}}\hat{{\bm{v}}}_{k}^{\sharp}+{\bm{\varepsilon}}\quad\text{with}\quad\left\lVert{\bm{\varepsilon}}\right\rVert\xrightarrow[p,n\to+\infty]{\text{a.s.}}0.$

Hence the result stated in Theorem 3.

##  IV Numerical Experiments

To illustrate this result, we conduct a first experiment on synthetic data
following model (1) with $K=3$ classes of equal size and
$(\lVert{\bm{\mu}}_{1}\rVert,\lVert{\bm{\mu}}_{2}\rVert,\lVert{\bm{\mu}}_{3}\rVert)=(3,4,5)$.
The ${\bm{x}}_{i}$’s are ordered by class. The spectral distribution of
${\bm{K}}$ is plotted in Figure 1 and Figure 2 shows the dominant eigenvectors
with the histograms of residuals
$\hat{{\bm{v}}}_{k}-\sqrt{\zeta_{k}}{\bm{v}}_{k}$. We observe a very good fit
of the latter to the probability density function of
${\mathcal{N}}(0,\frac{1-\zeta_{k}}{n})$ — the $\hat{{\bm{v}}}_{k}$’s exactly
correspond to a deterministic signal $\sqrt{\zeta_{k}}{\bm{v}}_{k}$ corrupted
by additive centered Gaussian noise. The signal $+$ noise structure of model
(1) has been transferred to the spectral estimator of ${\bm{V}}$.

Then, we conduct a second experiment on the Fashion-MNIST dataset [24]
consisting of $28\times 28$ images of clothes separated in $10$ classes of
size $7\,000$ each. We select two classes $k_{1},k_{2}$ and perform binary
spectral clustering using the dominant eigenvector of
${\bm{K}}=\frac{1}{p}{\bm{X}}^{\top}{\bm{X}}$ where the columns of ${\bm{X}}$
are the $784$ pixels of the images from classes $k_{1}$ and $k_{2}$. The
dimension of ${\bm{X}}$ is thus $784\times 14\,000$. Here, we assume a similar
model as our toy example in the introduction:
${\bm{X}}={\bm{\mu}}{\bm{j}}^{\top}+{\bm{W}}$ where $j_{i}=\pm 1$ depending on
the class of the $i$-th image. Thus, according to Theorem 3, the $i$-th entry
of the dominant eigenvector $\hat{{\bm{v}}}$ asymptotically follows
${\mathcal{N}}(\sqrt{\zeta}\frac{j_{i}}{\sqrt{n}},\frac{1-\zeta}{n})$ and,
given ${\bm{j}}$, $\zeta$ can be estimated as
$(\sum_{i=1}^{n}\frac{j_{i}}{\sqrt{n}}\hat{v}_{i})^{2}$. We can then compare
the observed accuracy
$\frac{1}{n}\sum_{i=1}^{n}{\mathbf{1}}_{\hat{v}_{i}j_{i}>0}$ to the one
expected from Theorem 3,
${\mathbb{P}}(\hat{v}_{i}j_{i}>0)\asymp\Phi(\sqrt{\frac{\zeta}{1-\zeta}})$.
The results are presented in Figure 3 for each pair of classes $k_{1},k_{2}$.

Figure 3: Observed and predicted classification accuracies of binary spectral
clustering on the Fashion-MNIST dataset [24]. The upper part (in blue) and
lower part (in orange) respectively give the observed and predicted
accuracies.

We find a very good agreement between the observed and predicted accuracies,
regardless of whether the problem is easy (e.g., Trouser vs Sandal) or hard
(e.g., Bag vs Ankle Boot). This observation confirms the general scope of
Theorem 3: starting from real data ${\bm{X}}$ which is clearly _not_ Gaussian,
the normal distribution naturally emerges in the fluctuations of the entries
of the large-dimensional eigenvector $\hat{{\bm{v}}}$.

##  V Conclusion

After recalling known results on spectral clustering under a general signal
$+$ noise random matrix model, we have shown that the entries of spiked
eigenvectors have Gaussian fluctuations in the large-dimensional regime. This
formalizes and clearly states a result which is often implicitly assumed in
many problems, without ever being actually proven. The proposed proof relies
solely on the rotational invariance of the noise. It is thus very general and
can easily be extended to most standard spike models. Numerical experiments
have demonstrated the universality of this phenomenon: the Gaussian behavior
of the entries of spike eigenvectors can even be observed on real unprocessed
data. This allows to accurately predict the classification performance of
spectral clustering. An interesting problem for future work is to understand
how these results extend to more exotic spike models such as [25].

## References

  * [1] J. Shi and J. Malik, “Normalized cuts and image segmentation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 22, no. 8, pp. 888–905, Aug. 2000, conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence. [Online]. Available: https://ieeexplore.ieee.org/document/868688
  * [2] C. Brew and S. S. im Walde, “Spectral clustering for german verbs,” in _Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)_ , 2002, pp. 117–124. [Online]. Available: https://aclanthology.org/W02-1016.pdf
  * [3] A. Ng, M. Jordan, and Y. Weiss, “On Spectral Clustering: Analysis and an algorithm,” in _Advances in Neural Information Processing Systems_ , vol. 14. MIT Press, 2002. [Online]. Available: https://papers.nips.cc/paper/2001/hash/801272ee79cfde7fa5960571fee36b9b-Abstract.html
  * [4] U. von Luxburg, “A tutorial on spectral clustering,” _Statistics and Computing_ , vol. 17, no. 4, pp. 395–416, Dec. 2007. [Online]. Available: https://doi.org/10.1007/s11222-007-9033-z
  * [5] C. Ding, X. He, H. Zha, M. Gu, and H. Simon, “A min-max cut algorithm for graph partitioning and data clustering,” in _Proceedings 2001 IEEE International Conference on Data Mining_ , Nov. 2001, pp. 107–114. [Online]. Available: https://ieeexplore.ieee.org/document/989507
  * [6] A. Onatski, M. J. Moreira, and M. Hallin, “Asymptotic power of sphericity tests for high-dimensional data,” _The Annals of Statistics_ , vol. 41, no. 3, pp. 1204–1231, Jun. 2013, publisher: Institute of Mathematical Statistics. [Online]. Available: https://projecteuclid.org/journals/annals-of-statistics/volume-41/issue-3/Asymptotic-power-of-sphericity-tests-for-high-dimensional-data/10.1214/13-AOS1100.full
  * [7] Z. Bai and J. W. Silverstein, _Spectral analysis of large dimensional random matrices_. Springer, 2010, vol. 20.
  * [8] L. A. Pastur and M. Shcherbina, _Eigenvalue Distribution of Large Random Matrices_ , ser. Mathematical Surveys and Monographs. American Mathematical Society, 2011, no. 171.
  * [9] R. Couillet and Z. Liao, _Random Matrix Methods for Machine Learning_. Cambridge: Cambridge University Press, 2022. [Online]. Available: https://www.cambridge.org/core/books/random-matrix-methods-for-machine-learning/6B681EB69E58B5F888EDB689C160C682
  * [10] J. Baik and J. W. Silverstein, “Eigenvalues of large sample covariance matrices of spiked population models,” _Journal of Multivariate Analysis_ , vol. 97, no. 6, pp. 1382–1408, Jul. 2006. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0047259X0500134X
  * [11] F. Benaych-Georges and R. R. Nadakuditi, “The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices,” _Advances in Mathematics_ , vol. 227, no. 1, pp. 494–521, May 2011. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0001870811000570
  * [12] R. Couillet and F. Benaych-Georges, “Kernel spectral clustering of large dimensional data,” _Electronic Journal of Statistics_ , vol. 10, no. 1, pp. 1393–1454, 2016, publisher: Shaker Heights, OH : Institute of Mathematical Statistics. [Online]. Available: https://hal.archives-ouvertes.fr/hal-01215343
  * [13] R. Couillet, F. Chatelain, and N. Le Bihan, “Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering,” _arXiv:2102.12293 [cs, stat]_ , May 2021, arXiv: 2102.12293. [Online]. Available: http://arxiv.org/abs/2102.12293
  * [14] A. Kadavankandy and R. Couillet, “Asymptotic Gaussian Fluctuations of Spectral Clustering Eigenvectors,” in _2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)_ , Dec. 2019, pp. 694–698.
  * [15] V. A. Marčenko and L. A. Pastur, “Distribution of eigenvalues for some sets of random matrices,” _Mathematics of the USSR-Sbornik_ , vol. 1, no. 4, p. 457, 1967, publisher: IOP Publishing.
  * [16] J. Baik, G. Ben Arous, and S. Péché, “Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices,” _The Annals of Probability_ , vol. 33, no. 5, pp. 1643–1697, Sep. 2005, publisher: Institute of Mathematical Statistics. [Online]. Available: https://projecteuclid.org/journals/annals-of-probability/volume-33/issue-5/Phase-transition-of-the-largest-eigenvalue-for-nonnull-complex-sample/10.1214/009117905000000233.full
  * [17] A. Lytova and L. Pastur, “Central limit theorem for linear eigenvalue statistics of random matrices with independent entries,” _The Annals of Probability_ , vol. 37, no. 5, pp. 1778–1840, 2009, publisher: Institute of Mathematical Statistics.
  * [18] N. El Karoui, “Concentration of measure and spectra of random matrices: Applications to correlation matrices, elliptical distributions and beyond,” _The Annals of Applied Probability_ , vol. 19, no. 6, pp. 2362–2405, Dec. 2009, publisher: Institute of Mathematical Statistics. [Online]. Available: https://projecteuclid.org/journals/annals-of-applied-probability/volume-19/issue-6/Concentration-of-measure-and-spectra-of-random-matrices--Applications/10.1214/08-AAP548.full
  * [19] C. Louart and R. Couillet, “Concentration of Measure and Large Random Matrices with an application to Sample Covariance Matrices,” Jan. 2021, arXiv:1805.08295 [math]. [Online]. Available: http://arxiv.org/abs/1805.08295
  * [20] R. Couillet and W. Hachem, “Fluctuations of Spiked Random Matrix Models and Failure Diagnosis in Sensor Networks,” _IEEE Transactions on Information Theory_ , vol. 59, no. 1, pp. 509–525, Jan. 2013, conference Name: IEEE Transactions on Information Theory. [Online]. Available: https://ieeexplore.ieee.org/document/6320635
  * [21] I. J. Schoenberg, “Metric Spaces and Completely Monotone Functions,” _Annals of Mathematics_ , vol. 39, no. 4, pp. 811–841, 1938, publisher: Annals of Mathematics. [Online]. Available: https://www.jstor.org/stable/1968466
  * [22] A. G. M. Steerneman and F. van Perlo-ten Kleij, “Spherical distributions: Schoenberg (1938) revisited,” _Expositiones Mathematicae_ , vol. 23, no. 3, pp. 281–287, Sep. 2005. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0723086905000034
  * [23] P. Billingsley, _Probability and Measure_ , ser. Wiley Series in Probability and Statistics. John Wiley & Sons, Inc., 2012.
  * [24] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms,” _arXiv:1708.07747 [cs, stat]_ , Sep. 2017, arXiv: 1708.07747. [Online]. Available: http://arxiv.org/abs/1708.07747
  * [25] H. Lebeau, R. Couillet, and F. Chatelain, “A Random Matrix Analysis of Data Stream Clustering: Coping With Limited Memory Resources,” in _Proceedings of the 39th International Conference on Machine Learning_. PMLR, Jun. 2022, pp. 12 253–12 281, iSSN: 2640-3498. [Online]. Available: https://proceedings.mlr.press/v162/lebeau22a.html