# Phase Contrast Microscopy Cell Population Segmentation: A Survey

Lin Zhang
<EMAIL_ADDRESS>University at Albany, SUNY

###### Abstract

Phase contrast microscopy (PCM) has been widely used in the biomedicine, which
allows users to observe objectives without staining or killing them. One
important related research is to employ PCM to monitor live cells. How to
segment cell populations in obtained PCM images gains more and more attention
as its a critical step for downstream applications, such as cell tracking,
cell classification and others. Many papers have been published to deal with
this problem from different perspectives. In this paper we aim to present a
comprehensive review on the development of PCM cell population segmentation.

###### keywords:

phase contrast microscopy (PCM), cell population segmentation

##  1 Introduction

Phase contrast microscopy was invented by Dutch physicist Frits Zernike [1]
using pure optical principles. In essence, cells are transparent and have
different refractive indexes, thus light will be differentiated into two parts
when goes through them: one remains the same, and the other is deviated. PCM
manipulates these two parts differently by using optics and phase rings to
convert the difference into visible intensity information, i.e. PCM images.
The main advantage of phase contrast microscopy is that cells will be
monitored in their natural state without being killed or stained like
previously methods, such as fluorescence. Therefore, the analysis on the
generated PCM images is critical to understand activities of cell. This paper
focuses on cell segmentation as this is an fundamental process for other
downstream applications, such as cell tracking [32], cell detection [19], cell
classification [41] and others.

Before we present existing methods, we give a formal definition of PCM cell
population segmentation problem. Given a PCM image that contains a group of
cells, we aim to segment each individual cell in it. There are three main
challenges in PCM cell population segmentation as below:

  * 1.

Densely populated cells: Since many cells cluster in a image, cell adhesion is
inevitable, therefore, the boundary between cells is unclear.

  * 2.

Cell shape deformation: A cell’s shape is uncertain due to its activities,
such as movements and cell events, such as apoptosis and mitosis, will change
the appearance of cells significantly.

  * 3.

Artifacts: Due to the imaging principle and imperfection of devices, images
often contains artifacts, such as bright halo and shade-off.

Therefore, this problem is different to other cell segmentation problems, such
as fluorescence microscopy cell segmentation [2, 3] and natural image
segmentation [4, 5]. In fluorescence microscopy cell images, cells are
colored, therefore, they are easy to be separated from their background. For
natural image segmentation, it has not artifacts as in PCM cell images, such
as bright halo and shade-off.

In the past years, many algorithms have been proposed to deal with PCM cell
population segmentation, however, a comprehensive survey on this problem is
still missing. A few papers [6, 7] presented partial survey relate to PCM cell
segmentation, however, these either too general or too narrow.

The remainder of this paper is structured as follows: A comprehensive analysis
of existing cell population segmentation methods is presented in Section 2. In
Section 3, we discuss related issues, including databases and performance
evaluation. The final conclusion will be given in Section 4.

##  2 Analytical methods of phase contrast microscopy cell population
segmentation

In this section, we review papers of phase contrast microscopy cell population
segmentation, which are summarized as three categories as below.

  * 1.

1\. Contour-based methods: These methods segment cells from surroundings by
using the contour information of cells.

  * 2.

2\. Machine Learning-based methods: These algorithms convert segmentation
problem into classification problem. The statistical models are learned to
distinguish cells and non-cell.

  * 3.

3\. Restoration-based methods: In contrast to other methods that treat phase
contrast microscopy images as natural images, these rule-based methods aim to
restore artifact-free images base on the imaging process of phase contrast
microscopy. Then we can perform cell segmentation on the obtain artifact-free
images by thresholding.

What needs illustration is that some methods could be assigned into multiple
categories and a discussion on this will be given this at the end of this
section. Next, we’ll analyze the motivation, approaches, and pros and cons of
each category.

###  2.1 Contour-based Methods

In this category, phase contrast microscopy cell population segmentation is
accomplished by detecting contours of cells. The underlying assumption is that
cells have clear boundaries and the variations within cells are small. These
rule-based methods can be roughly grouped into two class: Watershed based and
Active Contour based. The major problem with these Contour-based algorithms is
that contours of cells can be severely corrupted due to shape deformation,
artifacts and cell adhesion. Naturally, watershed and active contour methods
often produce over-segmentation and under-segmentation, respectively.

####  2.1.1 Watershed

Beucher et al. proposed a region based segmentation method called Watershed
segmentation [8]. The motivation of watershed segmentation came from water
flood in natural world that water will fill up basins and dams will prevent
water from different basins. The boundaries of objects in images are
corresponding to dams in nature and objects segmentation is achieved by
delineating boundaries of target objects. Watershed segmentation starts from
local minima, therefore, the success of watershed methods is based on the
right selection of local minima. Debeir [9] developed a marked watershed that
refines the initial local minima for segmentation. The selection of local
minima is converted into an classification problem, which uses an assemble
principle. Kachouie et al. [10] developed a coarse to refine method for
watershed segmentation. The first stage applies a template matching and canny
edge detection to find coarse regions of cells. The second stage utilizes
watershed transform to refine the obtained result. As appearances of cells are
not fixed, template matching is unable to detect cells with events or
movement. Wang et al. [11] applied cell peak detection and localization to
deal with cell adhesion. Each cell in a clustered region is defined by the
shortest distance between pixels and the detected peaks. However,this works
well only when the intensity distribution for each cell varies little, which
is not held in real-world due to the presence of artifacts and cell events.

Another common application of watershed is to combine with other segmentation
methods. For example, methods in [12, 13, 14] utilize the segmentation results
by watershed as the inputs of other methods for further segmentation. We’ll
introduce these methods in following sections.

####  2.1.2 Active Contour

Kass et al. [15] proposed the first active contour model. Specifically, the
best fit of contours is obtained by minimizing an energy function, also called
parametric active contours. While this model suffers from two major problems:
sensitive to the initial contours and incapability with concave contours. To
overcome these drawbacks, Xu [16] proposed the gradient vector flow (GVF)
model. Based on GVF, Zimmer et al. further presented a two-step model to
segment cells [17]. Firstly, the Canny edge map is employed to detect low
contrast boundaries. Secondly, a repulsive interaction is proposed to deal
with cell adhesion. The major drawback of this method is that the assumption
of homogeneous background in images.

In above parametric active contours methods, the parameters need to be
computed repeatedly until convergence. To avoid this, Caselles et al. [18]
developed another type of active contours, called geometric active contours.
Note that the relationship between geometric active contours and parametric
active contour is elaborated in [16]. Yang [19] introduced a geometric active
contours based method, called Narrow Band level set, [20]. The first step is
to extract the general position of cells using the gradient information in
images. Next, it employs a fast level set to get a refined segmentation from
the previous step. Tse et al. [12] proposed a segmentation method by combining
watershed and parametric active contour. Instead of using a single level set,
Vese et al. applied a multiphase level set[21] to extract more accurate
markers. Li [22] et al. presented two-stage level set based segmentation,
including morphological pre-segmentation and level set segmentation. The
morphological pre-segmentation is based on rolling-ball filter that segments
the background and cells. Then, it applies a naive level set to post-process
results from the last step. Gurari et. al.[7] presented a survey on six
popular level set methods’ performance on phase contrast microscopy cell data
and find the optimal one for each stage of cells’ evolution. However, this six
stages is not enough to cover all cases in cells’ activities, and thus might
not suitable for a large dataset.

This geometric active contour is still depend on curve messages, therefore,
these methods will fail when testing on a large data set with high complexity.

###  2.2 Machine Learning based methods

In these rule-based methods, PCM cell population segmentation is formulated as
a classification problem, which is to learn a statistical model to distinguish
cells and non-cell. The success of these methods depends on two factors:
sufficient training data and effective feature extraction. In the following,
we will present these methods according to their learning styles, including
supervised learning, unsupervised learning and semi-supervised and active
learning.

####  2.2.1 Supervised learning based methods

Methods in this group need to train models from the data with labels for all
pixels. Pan et al. proposed a cell population segmentation method using
Conditional Random Field(CRF) [23]. More formally, interesting pixels are
selected from local intensity minima [24] and used as the nodes in CRF graph.
The nodal potential and edge potential in CRF model are obtained by converting
the outputs of soft SVM [25] into posterior class probabilities. Another
method uses CRF to segment PCM cell population was presented in [26]. The
conventional CRF energy function only contains information from a single pixel
and pairwise pixels, which can be considered as the first-order and second-
order information respectively. However, phase contrast microscopy images are
often texture-less, therefore, this first-order and second-order information
is not enough for representing objects. Towards this, Kohli et al. [27]
developed a new energy function using $\mathcal{P}^{n}$ Potts potential
function. The energy function is written as below:

$E(S|I)=\underbrace{\sum_{p\in I}E_{1}(S_{p}|I)}_{first-
order}+\underbrace{\sum_{p,q\in I}E_{2}(S_{p},S_{q}|I)}_{second-
order}+\underbrace{\sum_{C\in I}E_{C}(S_{C}|I)}_{higher-order},$ (1)

where $S_{p}$ is a pixel and $S_{q}$ is its neighbor; $C$ a clique in the
image. The $\mathcal{P}^{n}$ Potts potential is a higher order clique
potential of arbitrary clique size. He et al. proposed a two-stage method
combining machine learning and shape information in cells. Cells are segmented
via a learning model and further refined by curve evolution [28]. Here, it
defines features of cells as intensity distribution, gradient magnitude
Distribution, and Earth Mover’s Distance. Wang et al. [14] integrate AdaBoost
with SVM to perform PCM cell population segmentation. This method contains
three tasks: cell detection, foreground segmentation, and individual cell
segmentation. An AdaBoost classifier is trained by using Mexican Hat wavelet
features for detecting cell centers. The detection result is used to as the
seed of watershed segmentation for the segmentation of whole cells.
Experimental results show that methods in [14, 28] fail to segment clustered
cells due to watershed method has genetic problem of dealing with cell
adhesion.

Funke et al. [13] introduced hierarchical method for PCM cell population
segmentation problem. Firstly, a Random Forest classifier [29] is applied to
obtain the boundaries of cells. This followed by a watershed segmentation to
get rough cells. Secondly, it applies a structured SVM classifier [30] to
learned a cost function for extracting accurate boundary of cells. This method
needs neither manually feature engineer nor parameter tuning, which reduces
human interference.

Li et al. [22, 32] solved the PCM cell segmentation problem using a Bayesian
classifier. It extracts color histograms as features for training a model. Yin
et al. [33] also addressed this problem using a Bayesian classifier. The
feature of pixels is computed based on intensity histogram in a neighbouring
window, and is compressed by clustering to reduce redundancy.

####  2.2.2 Unsupervised learning based methods

Since labeling pixels is often expensive, unsupervised learning style is
another option to deal with PCM cell population segmentation. Mualla et al.
[34] presented a two-step clustering scheme for this problem. The first step
is to detect cells using the scale invariant feature transform (SIFT) feature
[35]. To separate cells from the background, it employs a two class K-medians
clustering, where it uses difference of gaussian (DOG) and local variance as
features. The final cell segmentation is also implemented based on clustering,
in particular, the number of clusters is obtained by a self-labeling algorithm
[24].

Zhang et al. [36] developed a segmentation method based on Random Forest and
correlation clustering. Similar to [13], Random Forest classifier [29] is used
to identify the boundary of cells. Then, it constructs superpixels based on
the resulting boundary probability and obtains an adjacency graph by weighting
superpixels. The final cell segmentation is converted into a graph
partitioning problem.

Instead of using natrual image features as in [34, 36], Su et al. [39]
introduced a new feature by taking advantages of PCM imaging principles,
called phase retardation feature. The key is to partition images by clustering
pixels, where it computes pairwise similarities using phase retardation
features. Note that this feature depend on research on methods in section 2.3.

####  2.2.3 Semi-supervised and Active learning

Both Semi-supervised and Active learning need a limit number of labels for
training, therefore, this is a merit in dealing with the PCM cell segmentation
problem due to the limit access to labels.

Su et al. [41] first proposed a method that uses semi-supervised learning
architecture to segment cells in PCM images . It learns a dictionary using the
proposed retardation features, which will be elaborated in Section 2.3. Next,
each pixel is represented by a coefficient vector using the obtained
dictionary, where these pixels have labels. This is followed by a label
propagation to infer cells in the unlabeled data over an affinity matrix that
characterizes the relationship between unlabeled atoms and labeled atoms,
which is to optimize the following objective:

$f({\bf Y}_{u})=trace\left([{\bf Y}_{l};{\bf Y}_{u}]^{T}{\bf
L}\begin{bmatrix}{\bf Y}_{l}\\\ {\bf Y}_{u}\end{bmatrix}\right)$ (2)

where ${\bf L}$ is a Laplacian matrix; ${\bf Y}_{l}$ and ${\bf Y}_{u}$ are the
matrices of labeled and unlabeled atoms, respectively. The final segmentation
result ${\bf Y}_{u}^{*}$ is computed as:

${\bf Y}_{u}^{*}={\bf L}_{uu}^{-1}{\bf W}_{ul}{\bf Y}_{l}$ (3)

where ${\bf W}_{ul}$ represent similarity between unlabeled and labeled atoms.
In order to lower human intervention in this method, Su et al. [42] developed
a method that combines semi-supervised learning and active learning. They
first detect errors from the results of semi-supervised segmentation, and then
correct them by a human. Next, the corrected information will be propagated
over the whole graph to fix other similar errors. These two steps will be
alternatively proceed until all errors are eliminated. To further minimize
human intervention, Su et al. [44] improved both the error detection criterion
and information propagation strategy in [42]. Different to the affinity matrix
updating strategy in [42] that propagates information to whole graph in each
iteration, Su et al. developed an faster solution using augmented graph [46],
in which only a part of the matrix will be updated in each iteration. Although
experimental results show excellent performance in PCM cell population
segmentation, one potential weakness of active learning based methods is that
the error collection must be comprehensive, otherwise, these methods will fail
when the errors in the testing are different from those in the training data.

###  2.3 Restoration based methods

In previous categories, all methods treat PCM images as natural images and
employ methods from natural images’ analysis. However, this neglects the
difference between PCM images and natural images due to their significant
different imaging principles. In this section, we focus on methods of dealing
PCM image cell population segmentation by analyzing its underlying structures.
The phase contrast microscopy imaging system is composed of Microscope and
Camera devices, as shown in Figure 1 [47]. Under this system, the light (L)
passes through cells and optics, then produces the irradiance (E) for
observation by eyes or cameras. Recently, several methods have been proposed
to model this imaging process and convert cell segmentation as a restoration
problem. For example, methods in [48, 49, 50, 41] formulate the imaging
procedure as a linear model. Besides, methods [47, 51] have been trying to
estimate the relationship between exposure duration and intensities with a
cell-sensitive camera response function from the camera part. In both methods,
cells are restored and cell segmentation can be implemented by simple
thresholding.

Figure 1:  Phase contrast microscopy imaging model

####  2.3.1 Preconditioning

In this approach, researchers restore artifact-free microscopy images by
approximating PCM imaging system as a regularized quadratic model. Li et al.
[52] first demonstrated that Differential Interference Contrast (DIC)
microscopes imaging system can be approximated by a linear imaging model.
Inspired by this work, Yin et al. [48, 49] proposed a preconditioning
algorithm, where cells in PCM images can be segmented from a restored
artifact-free image by thresholding. More formally, this model is written as
as follows:

$\mathbf{g}\approx\mathbf{Hf}$ (4)

where $\mathbf{H}$ is the convolution kernel using the point spread function
(PSF); $\mathbf{g}$ is the observed image and $\mathbf{f}$ is the artifact-
free image. This is solved by an iterative algorithm [53].

In [48, 49], the underlying assumption is that the phase retardation caused by
cells is tiny, almost zero. However, this assumption does not hold in
practical due to the presence of bright cells like mitosis and apoptosis
cells. To fix this, Su etc. [50] improved this model by generalizing the phase
retardation $\theta(x)$ as a linear combination as below:

$e^{i\theta(x)}\approx\sum_{m=0}^{M-1}\varphi_{m}(x)e^{i\theta(m)},s.t.\varphi_{m}(x)\geq
0$ (5)

where
$\theta_{m}=0,\frac{2\pi}{M},...,\frac{2m\pi}{M},...\frac{2(M-1)\pi}{M}$,
$\varphi_{m}(x)$ is the coefficient. Then the restoration problem can be
converted to the following optimization problem:

$\displaystyle{\min\sum_{k=0}^{N-1}\left\\{\left\|\Psi_{mk}\right\|_{1}+\omega_{s}\
\Psi_{mk}^{T}\mathbf{L}\Psi_{mk}\right\\},\begin{Bmatrix}\left\|g-\sum_{k=0}^{N-1}\mathbf{H}_{mk}\Psi_{mk}\right\|_{2}<\varepsilon\\\
\Psi_{mk}^{T}\geq 0\end{Bmatrix}}$ (6)

where $\bf L$ is a Laplacian matrix to describe similarity between spatial
pixel neighbors; $\mathbf{\Psi}$ is the vectorized coefficient matrix. Each
pixel in the images is represented by a feature vector
$\left\\{\Psi_{m1},\Psi_{m2},....\Psi_{mk}\right\\}$. The segmentation is
accomplished by K-means clustering on the obtained feature vectors.

####  2.3.2 Cell-sensitive phase contrast microscopy Imaging

In contrast to preconditioning methods that focus on microscope imaging part,
Zhao et atl. [47, 51] developed methods by taking advantage of camera
information in the PCM system. The motivation is that different exposure
duration $\Delta t$ of the camera will change the image intensity $I$ as below

$I=f(E\Delta t)$ (7)

where $f$ is the camera response function. To estimate $f$ , the following
optimization problem is formulated:

$\displaystyle O(g,E)=\sum_{i=0}^{N}\sum_{j=0}^{P}\left\\{g(I_{ij})-\log
E_{i}-\log\Delta t_{j}\right\\}^{2}$ (8)
$\displaystyle+\alpha\sum_{i\in[1,N]}(\log
E_{i})^{2}+\beta\sum_{I}[\omega(I)g^{{}^{\prime\prime}}(I)]^{2}$

where $E_{i}$ is the irradiance at the $i_{th}$ pixel; $I_{ij}$ is the
intensity at the $i_{th}$ pixel with exposure duration $\Delta t_{j}$. By
taking the derivatives of $g$ and $E$ and equating to zero, this problem will
be converted to an overdetermined problem, which can be addressed by a
singular value decomposition method. Once the camera response function $f$ is
estimated, the irradiance $E_{i}$ can be obtained based on its pixel values:

$\log E_{i}=\frac{\sum_{j=1}^{P}\omega(I_{ij})(g(I_{ij})-\Delta
t_{j})}{\sum_{j=1}^{P}\omega(I_{ij})}$ (9)

A high contrast map between cells and background is then obtained, as shown in
Figure 2. Therefore, cell segmentation is accomplished by simply thresholding.

Figure 2: cell sensitive segmentation, (a)Restored irradiance image; (b)
Irradiance map

Later on, another segmentation method was developed by analyzing camera
exposure [56], which computes Maximally Stable Extremal Regions(MSER) [57]
under each exposure settings. It gets a binary map of cells by accumulating
these obtained MMSERs using the frequency of pixels in each MMSER. The final
segmentation is accomplished by applying a Graph-cut on MMSER.

###  2.4 Discussion

We reviewed PCM cell population segmentation methods in three major
categories. Note that some methods can be assigned into multiple categories.
For example, some unsupervised learning methods [36, 39] employ ideas from
restoration based methods.

The Contour-based methods heavily rely on boundaries information of cells.
However, such information in PCM images is unreliable because of the shape
deformation and artifacts. Therefore, these rule-based methods have an obvious
limit on PCM cell population segmentation.

For machine learning methods, these aim to find statistical models of cells.
The key to the success is extracting representative features. While
traditional hand-crafted features have limited power since PCM cell images are
textureless. It is promising to integrate deep learning for feature
extraction. Furthermore, machine learning based methods depend on training
datasets and labels. With only a small amount of labeled data are available,
semi-supervised learning, active learning and unsupervised learning methods
have more potentials than supervised learning methods.

Restoration based methods are the most effective method, however, these
methods are often having high computation costs, which is not suitable for a
large-scale datasets. Due to the high complexity, fast solutions of these
methods are needed to reduce costs.

##  3 Database and Performance Evaluation

Although many PCM cell population segmentation methods have been developed
many years, only a few methods have experimented on large-scale datasets,
which contain a large number of images and each image has a high density of
cells. Moreover, researchers evaluate their methods on different datasets
using different evaluation measures. These raise concerns on the performance
evaluation and comparison. In this section, we aim to give a review on the
characteristics of public phase contrast microscopy cell image datasets and
commonly used evaluation metrics in this topic.

Figure 3: Sample images from [23]: bovine aortic endothelial cells

Figure 4: Sample images used in [47, 51]: with exposure of 100ms, 500ms

Figure 5: Sample images used in [7]

###  3.1  Phase Contrast Microscopy cell Image Datasets

The database applied in [23] consists of two different types of cells: bovine
aortic endothelial cells and C2C12 muscle stem cells ,which is available at
http://www.albany.edu/celltracking/downloads.html. Each type of cell has 10
training images and 10 testing images. The average number of cells in bovine
aortic endothelial cells images and C2C12 muscle stem cells images are 4,900
and 9,800, respectively. We show two samples from this data as in Fig. 3. The
database used in [41, 49, 50, 44, 42] contains three different kind of cells
images, which are bovine aortic endothelial cells, C2C12 stem cells and muscle
stem cells, which is available at
http://www.albany.edu/celltracking/downloads.html. The detail specifications
are presented in Table 1, and some sample images are shown in Fig. 6. Li et
al. created a dataset [22, 32] contains two image sequences of MG-63
osteosarcoma cells with 150 frames and another two sequences of proprietary
amnion epithelial stem cells with 256 frames. In [47, 51], cell images are
obtained in six different exposure durations( [50 100 200 300 400 500]ms) for
three different cell dishes, as shown in Fig. 4. The cell database from BU-BIL
[7] contains 235 images in total and 152 are phase contrast images, which 35
rat smooth muscles cells, 70 rabbit smooth muscle cells, and 47 fibroblasts,
which is available at http://www.cs.bu.edu/∼betke/BiomedicalImageSegmentation.
We show some samples in Fig. 5.

Table 1: Database specifications

| Image Number | Cell number per image | Image size | Type of cell
---|---|---|---|---
Sequence 1 | 589 |  500$\sim$800+ | 1040x1392 | bovine aortic endothelial cell
Sequence 2 | 632 |  50$\sim$300+ | 696x520 | muscle stem cell
Sequence 3 | 383 | 300+ | 1040x1392 | C2C12 myoblastic stem cell

Figure 6: Sample images used in [41, 49, 50, 44, 42]

###  3.2 Performance Evaluation

Most papers of phase contrast microscopy cell population segmentation are
evaluated on different databases rather than a few public benchmark datasets.
In fact, only a few of them are tested a common database, where we show the
comparison of them in Table 2. So far, the commonly used metric in this topic
are accuracy, precision, recall, Normalized Probabilistic Rand index (NPR)
[58], Tannimoto coefficient (TC). These can be roughly grouped into two major
categories: pixel-level and cell-level metric, where NPR belongs to cell-level
measure and the others are pixel-level measures. The successful cell
segmentation should not only count the number of segmented pixels but also
measure whether or not these pixels belong to corresponding cells. Therefore,
both cell-level and pixel-level measures should be considered in the
evaluation criterion.

Table 2: Segmentation results on the same database (Acc: Accuracy, Re: Recall;
Pre: Precision)

Methods |  Sequence 1 | Sequence 2 | Sequence 3
---|---|---|---
Acc | TC | NPR | F | Re | Pre | Acc | TC | NPR | F | Re | Pre | Acc | TC | NPR | F | Re | Pre
Precoditioning [49] | 0.97 | 0.83 | 0.75 | 0.8676 | 0.858 | 0.878 | 0.9 | 0.31 | 0.27 | 0.1749 | 0.157 | 0.348 |  |  |  | 0.3212 | 0.347 | 0.314
Generalized precoditioning. [50] |  |  |  | 0.9319 | 0.921 | 0.943 |  |  |  | 0.9319 | 0.942 | 0.967 |  |  |  | 0.9412 | 0.932 | 0.963
Semi-supervised learning[41] |  | 0.94 | 0.88 |  | 0.963 | 0.893 |  | 0.92 | 0.92 |  | 0.979 | 0.863 |  |  |  |  |  |
Bayesian classifier[33] |  |  |  | 0.93 | 0.9 | 0.967 |  |  |  | 0.911 | 0.925 | 0.898 |  |  |  | 0.893 | 0.854 | 0.936
Clustering [39] |  |  | 0.87 |  |  |  |  |  | 0.85 |  |  |  |  |  |  |  |  |
Active learning 1[42] |  |  | 0.95 |  |  |  |  |  | 0.95 |  |  |  |  |  | 0.95 |  |  |
Bounded Active learning[44] | 0.96 |  |  |  |  |  | 0.96 |  |  |  |  |  | 0.96 |  |  |  |  |

##  4 CONCLUSION

This paper aims to present a thorough study of phase contrast microscopy cell
population segmentation, including methodologies, datasets and metrics. We
present the motivation, general steps, and pros and cons for methods in this
area. We also highlight two important open issues in this problem, which are
the missing of benchmark datasets and inconsistent evaluation metrics. We hope
researchers in this community can build a benchmark dataset and a unified
metric for better comparison.

##  5 Reference

## References

  * [1] F. Zernike, How i discovered phase contrast, Annals of Physics 121 (1955) 345–349.
  * [2] O. Dzyubachyk, J. Essers, W. A. v. Cappellen, C. Baldeyron, A. Inagaki, W. J. Niessen, E. Meijering, Automated analysis of time-lapse fluorescence microscopy images: from live cell images to intracellular foci, Bioinformatics 26 (19) (2010) 2424–2430.
  * [3] J.-P. Bergeest, K. Rohr, Fast globally optimal segmentation of cells in fluorescence microscopy images, Medical Image Computing and Computer-Assisted Intervention – MICCAI 2011: 14th International Conference, Toronto, Canada, September 18-22, 2011, Proceedings, Part I (2011) 645–652.
  * [4] Z. Liu, X. Li, P. Luo, C.-C. Loy, X. Tang, Semantic image segmentation via deep parsing network (2015) 1377–1385.
  * [5] C. Rupprecht, L. Peter, N. Navab, Image segmentation in twenty questions (2015) 3314–3322.
  * [6] E. Meijering, Cell segmentation: 50 years down the road, IEEE Signal Processing Magazine 29 (2012) 140–145.
  * [7] D. Gurari, D. Theriault, M. Sameki, M. Betke, How to use level set methods to accurately find boundaries of cells in biomedical images? evaluation of six methods paired with automated and crowdsourced initial contours., The Interactive Medical Image Computation Workshop (IMIC), in conjunction with MICCAI 2014, 29 (2014) 9.
  * [8] S. Beucher, L.~́ejou, Use of watersheds in contour detection., In Proc. International Workshop on Image Processing, Real-Time Edge and Motion Detection/Estimation.
  * [9] O. Debeir, I. Adanja, N. Warzee, P. V. Ham, C. Decaestecker, Phase contrast image segmentation by weak watershed transform assembly, 2008 5th IEEE International Symposium on Biomedical Imaging: From Nano to Macro (2008) 724–727.
  * [10] N. N. Kachouie, P. Fieguth, E. Jervis, Watershed deconvolution for cell segmentation, 2008 30th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (2008) 375–378.
  * [11] Y. Wang, Z. Zhang, H. Wang, S. Bi, Segmentation of the clustered cells with optimized boundary detection in negative phase contrast images, PLoS ONE 10 (2015) 1–19.
  * [12] S. Tse, L. Bradbury, J. W. Wan, H. Djambazian, R. Sladek, T. Hudson, A combined watershed and level set method for segmentation of brightfield cell images, Proc. SPIE 7259, Medical Imaging 2009: Image Processing,72593G.
  * [13] C. Jan Funke, Fred A. Hamprecht, Learning to segment: Training hierarchical segmentation under a topological loss, Medical Image Computing and Computer-Assisted Intervention MICCAI 9351 (2015) 268–275.
  * [14] Z. Q. R. M. D. M. E. W. Xiaoxu Wang, Weijun He, Cell segmentation for division rate estimation in computerized video time-lapse microscopy, Book chapter in Microscopic Image Analysis for Life Science Applications,published by Artech. House, Inc. 6431.
  * [15] M. Kass, A. Witkin, D. Terzopoulos, Snakes: Active contour models, International Journal of Computer Vision 1 (4) (1988) 321–331.
  * [16] C. Xu, A. Yezzi, J. J. L.Prince, On the relationship between parametric and geometric active contours., In Proc. Of 34th Asilomar Conference on Signal, System, and Comouters (2000) pp.483–489.
  * [17] C. Zimmer*, E. Labruyère, V. Meas-Yedid, N. Guillén, J.-C. Olivo-Marin, Segmentation and tracking of migrating cells in video microscopy with parametric active contours: A tool for cell-based drug testing., IEEE TRANSACTIONS ON MEDICAL IMAGING 21 (2002) NO.10.
  * [18] Caselles, F. Catte, T. Coll, F. Dibos, A geometric model for active contours, IEEE TRANSACTIONS ON MEDICAL IMAGING 66 (1993) 1–31.
  * [19] F. Yang, M. A. Mackey, F. Ianzini, G. Gallardo, M. Sonka, Cell segmentation, tracking, and mitosis detection using temporal context, Medical Image Computing and Computer-Assisted Intervention(MICCAI): 8th International Conference (2005) 302–309.
  * [20] D. Adalsteinsson, J. A. Sethian, A fast level set method for propagating interfaces, JOURNAL OF COMPUTATIONAL PHYSICS 118 (1994) 269–277.
  * [21] L. A. Vese, T. F. Chan, A multiphase level set framework for image segmentation using the mumford and shah model, International Journal of Computer Vision 50 (3) (2002) 271–293.
  * [22] L. Kang, C. Mei, K. Takeo, W. LE, C. PG, Cell population tracking and lineage construction with spatiotemporal context, Medical Image Computing and Computer-Assisted Intervention – MICCAI (2007) 295–302.
  * [23] J. Pan, T. Kanade, M. Chen, Heterogeneous conditional random field: Realizing joint detection and segmentation of cell regions in microscopic images, Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on (2010) 2940–2947.
  * [24] J. Pan, T. Kanade, M. Chen, Learning to detect different types of cells under phase contrast microscopy, Microscopic Image Analysis with Applications in Biology (MIAAB) 2009 (CMU-RI-TR).
  * [25] C. Bishop, Pattern recognition and machine learning, Springer.
  * [26] C. Restif, C. Russell, D. Metaxas, P. Torr, Using the pn potts model with learning methods to segment live cell images,, 2007 11th IEEE International Conference on Computer Vision (ICCV), 00 (2007) 1–8.
  * [27] P. Kohli, M. P. Kumar, P. H. S. Torr, P3 beyond: Solving energies with higher order cliques,, in Proc. IEEE Conf. Computer Vision and Pattern Recog- nition (CVPR), 30 (2007) 1–8.
  * [28] W. He, X. Wang, D. Metaxas, R. Mathew, E. White, Cell segmentation for division rate estimation in computerized video time-lapse microscopy, Proc. SPIE 6431 (2007) 643109–643109–8.
  * [29] C. Sommer, C. Straehle, U. Koethe, F. A. Hamprecht, ilastik: Interactive learning and segmentation toolkit, In ISBI.
  * [30] I. Tsochantaridis, T. Hofmann, T. Joachims, Y. Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the Twenty-first International Conference on Machine Learning (2004) 104–.
  * [31] sbmrm, Bundle method for structured risk minimization., https://github.com/ funkey/sbmrm.
  * [32] K. Li, M. Chen, T. Kanade, E. D. Miller, L. E. Weiss, P. G. Campbella, Cell population tracking and lineage construction using multiple-model dynamics filters and spatiotemporal optimization., Med Image Anal. 12 (5) (2008) 546–566.
  * [33] Z. Yin, R. Bise, M. Chen, T. Kanade, Cell segmentation in microscopy imagery using a bag of local bayesian classifiers, 2010 IEEE International Symposium on Biomedical Imaging: From Nano to Macro (2010) 125–128.
  * [34] F. Mualla, S. Schöll, B. Sommerfeldt, A. Maier, S. Steidl, R. Buchholz, J. Hornegger, Unsupervised unstained cell detection by sift keypoint clustering and self-labeling algorithm, Medical Image Computing and Computer-Assisted Intervention – MICCAI 2014.
  * [35] F. Mualla, S. Schöll, B. Sommerfeldt, A. Maier, J. Hornegger, Automatic cell detection in bright-field microscope images using sift, random forests, and hierarchical clustering, IEEE Transactions on Medical Imaging 32 (12) (2013) 2274–2286.
  * [36] Z. Zhang, J. Yarkony, F. A. Hamprecht, Cell detection and segmentation using correlation clustering, Medical Image Computing and Computer-Assisted Intervention – MICCAI 2014: 17th International Conference, Boston, MA, USA (2014) 9–16.
  * [37] B. Andres, J. H. Kappes, T. Beier, U. Köthe, F. A. Hamprecht, Probabilistic image segmentation with closedness constraints, ICCV.
  * [38] I. A. F. C. C. Yarkony, Julian, Fast planar correlation clustering for image segmentation, Computer Vision – ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012, Proceedings, Part VI (2012) 568–581.
  * [39] H. Su, Z. Yin, S. Huh, T. Kanade, Cell segmentation via spectral analysis on phase retardation features, 2013 IEEE 10th International Symposium on Biomedical Imaging (2013) 1477–1483.
  * [40] T. M. Cover, J. A. Thomas, Elements of information theory,, Wiley-Interscience, New York, NY, USA.
  * [41] H. Su, Z. Yin, S. Huh, T. Kanade., Cell segmentation in phase contrast microscopy images via semi-supervised classification over optics-related features, Med. Image Anal. 17 (2013) 746– 765.
  * [42] H. Su, Z. Yin, T. T., S. Huh, Interactive cell segmentation based on correction propagation, Biomedical Imaging (ISBI), 2014 IEEE 11th International Symposium on.
  * [43] T.M.Cover, J.A.Thomas., Elements of information theory., Wiley-Interscience.
  * [44] H. Su, Z. Yin, T. S. H. Kanade, Active sample selection and correction propagation on a gradually-augmented graph, IEEE Conference on Computer Vision and Pattern Recognition(CVPR).
  * [45] R. El-Yaniv, D. Pechyony, Transductive rademacher complexity and its applications, Learning Theory: 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA; June 13-15, 2007. Proceedings (2007) 157–171.
  * [46] X. Zhu, J. Lafferty, Z. Ghahramani, Combining active learning and semi-supervised learning using gaussian fields and harmonic functions, ICML 2003 workshop on The Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining (2003) 58–65.
  * [47] Z. Yin, H. Su, E. Ker, M. Li, H. Li., Cell sensitive phase contrast microscopy imaging by multiple exposures, Medical Image Analysis (MedIA).
  * [48] Z. Yin, T. Kanade, Restoring artifact-free microscopy image sequences, 2011 IEEE International Symposium on Biomedical Imaging: From Nano to Macro (2011) 909–913.
  * [49] Z. Yin, T. Kanade, M. Chen, Understanding the phase contrast optics to restore artifact-free microscopy images for segmentation., Medical Image Analysis 16 (5) (2012) 1047–1062.
  * [50] H. Su, Z. Yin, T. Kanade, S. Huh, Phase contrast image restoration via dictionary representation of diffraction patterns, Medical Image Computing and Computer-Assisted Intervention – MICCAI (2012) 615–622.
  * [51] Z. Yin, H. Su, E. Ker, M. Li, H. Li., Cell-sensitive microscopy imaging for cell image segmentation, Medical Image Computing and Computer-Assisted Intervention – MICCAI 8673 (2014) 41–48.
  * [52] K. Li, T. Kanade, Nonnegative mixed-norm preconditioning for microscopy image segmentation, Proc. Int. Conf. Info. Processing Med. Imaging (IPMI).
  * [53] F. Sha, Y. Lin, L. K. Saul, D. D. Lee, Multiplicative updates for nonnegative quadratic programming, Neural Comput. 19 (8) (2007) 2004–2031.
  * [54] D. Needell, R. Vershynin, Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit, Selected Topics in Signal Processing, IEEE Journal of 4 (2010) 310 –316.
  * [55] F. Sha, Y. Lin, L. Saul, D. Lee, Multiplicative updates for nonnegative quadratic programming, Neural Comput. 19 (2007) 2004–2031.
  * [56] M. Li, Z. Yin, Cell segmentation using stable extremal regions in multi-exposure microscopy images, 2016 IEEE 13th International Symposium on Biomedical Imaging (ISBI) (2016) 526–530.
  * [57] J. Matas, O. Chum, M. Urban, T. Pajdla, Robust wide-baseline stereo from maximally stable extremal regions, Image and vision computing 22 (10) (2004) 761–767.
  * [58] R. Unnikrishnan, C. Pantofaru, M. Hebert, A measure for objective evaluation of image segmentation algorithms, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05) - Workshops (2005) 34–34.


* Azar et al., (2013) Azar, M. G., Munos, R., and Kappen, H. J. (2013).  Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.  Machine learning, 91(3):325–349.
  * Beck, (2017) Beck, A. (2017).  First-order methods in optimization.  SIAM.
  * Bhandari, (2020) Bhandari, J. (2020).  Optimization Foundations of Reinforcement Learning.  PhD thesis, Columbia University.
  * Bhandari and Russo, (2019) Bhandari, J. and Russo, D. (2019).  Global optimality guarantees for policy gradient methods.  arXiv preprint arXiv:1906.01786.
  * Bhandari and Russo, (2020) Bhandari, J. and Russo, D. (2020).  A note on the linear convergence of policy gradient methods.  arXiv preprint arXiv:2007.11120.
  * Cai et al., (2019) Cai, Q., Yang, Z., Jin, C., and Wang, Z. (2019).  Provably efficient exploration in policy optimization.  arXiv preprint arXiv:1912.05830.
  * Cen et al., (2020) Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. (2020).  Fast global convergence of natural policy gradient methods with entropy regularization.  arXiv:2007.06558, accepted to Operations Research.
  * Cen et al., (2021) Cen, S., Wei, Y., and Chi, Y. (2021).  Fast policy extragradient methods for competitive games with entropy regularization.  arXiv preprint arXiv:2105.15186.
  * Ding et al., (2020) Ding, D., Zhang, K., Basar, T., and Jovanovic, M. (2020).  Natural policy gradient primal-dual method for constrained markov decision processes.  Advances in Neural Information Processing Systems, 33.
  * Du et al., (2017) Du, S., Jin, C., Jordan, M., Póczos, B., Singh, A., and Lee, J. (2017).  Gradient descent can take exponential time to escape saddle points.  In Advances in Neural Information Processing Systems, pages 1068–1078.
  * Fazel et al., (2018) Fazel, M., Ge, R., Kakade, S., and Mesbahi, M. (2018).  Global convergence of policy gradient methods for the linear quadratic regulator.  In International Conference on Machine Learning, pages 1467–1476.
  * Jansch-Porto et al., (2020) Jansch-Porto, J. P., Hu, B., and Dullerud, G. (2020).  Convergence guarantees of policy optimization methods for Markovian jump linear systems.  arXiv preprint arXiv:2002.04090.
  * Kakade, (2002) Kakade, S. M. (2002).  A natural policy gradient.  In Advances in neural information processing systems, pages 1531–1538.
  * Khamaru et al., (2020) Khamaru, K., Pananjady, A., Ruan, F., Wainwright, M. J., and Jordan, M. I. (2020).  Is temporal difference learning optimal? an instance-dependent analysis.  arXiv preprint arXiv:2003.07337.
  * Khodadadian et al., (2021) Khodadadian, S., Doan, T. T., Maguluri, S. T., and Romberg, J. (2021).  Finite sample analysis of two-time-scale natural actor-critic algorithm.  arXiv preprint arXiv:2101.10506.
  * Konda and Tsitsiklis, (2000) Konda, V. R. and Tsitsiklis, J. N. (2000).  Actor-critic algorithms.  In Advances in neural information processing systems, pages 1008–1014.
  * Lan, (2021) Lan, G. (2021).  Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes.  arXiv preprint arXiv:2102.00135.
  * Lee et al., (2016) Lee, J. D., Simchowitz, M., Jordan, M. I., and Recht, B. (2016).  Gradient descent only converges to minimizers.  In Conference on learning theory, pages 1246–1257. PMLR.
  * Liu et al., (2019) Liu, B., Cai, Q., Yang, Z., and Wang, Z. (2019).  Neural proximal/trust region policy optimization attains globally optimal policy.  arXiv preprint arXiv:1906.10306.
  * Liu et al., (2020) Liu, Y., Zhang, K., Basar, T., and Yin, W. (2020).  An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods.  Advances in Neural Information Processing Systems, 33.
  * Mei et al., (2021) Mei, J., Gao, Y., Dai, B., Szepesvari, C., and Schuurmans, D. (2021).  Leveraging non-uniformity in first-order non-convex optimization.  arXiv preprint arXiv:2105.06072.
  * (25) Mei, J., Xiao, C., Dai, B., Li, L., Szepesvári, C., and Schuurmans, D. (2020a).  Escaping the gravitational pull of softmax.  Advances in Neural Information Processing Systems, 33.
  * (26) Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2020b).  On the global convergence rates of softmax policy gradient methods.  In International Conference on Machine Learning, pages 6820–6829. PMLR.
  * Mnih et al., (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015).  Human-level control through deep reinforcement learning.  Nature, 518(7540):529–533.
  * Mohammadi et al., (2019) Mohammadi, H., Zare, A., Soltanolkotabi, M., and Jovanović, M. R. (2019).  Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem.  arXiv preprint arXiv:1912.11899.
  * Pananjady and Wainwright, (2020) Pananjady, A. and Wainwright, M. J. (2020).  Instance-dependent $\ell_{\infty}$-bounds for policy evaluation in tabular reinforcement learning.  IEEE Transactions on Information Theory, 67(1):566–585.
  * Peters and Schaal, (2008) Peters, J. and Schaal, S. (2008).  Natural actor-critic.  Neurocomputing, 71(7-9):1180–1190.
  * Puterman, (2014) Puterman, M. L. (2014).  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons.
  * Schulman et al., (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015).  Trust region policy optimization.  In International conference on machine learning, pages 1889–1897.
  * Schulman et al., (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017).  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347.
  * Shani et al., (2019) Shani, L., Efroni, Y., and Mannor, S. (2019).  Adaptive trust region policy optimization: Global convergence and faster rates for regularized MDPs.  arXiv preprint arXiv:1909.02769.
  * Silver et al., (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016).  Mastering the game of Go with deep neural networks and tree search.  nature, 529(7587):484–489.
  * Sutton, (1984) Sutton, R. S. (1984).  Temporal credit assignment in reinforcement learning.  PhD thesis, University of Massachusetts.
  * Sutton et al., (2000) Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y. (2000).  Policy gradient methods for reinforcement learning with function approximation.  In Advances in neural information processing systems, pages 1057–1063.
  * Tu and Recht, (2019) Tu, S. and Recht, B. (2019).  The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint.  In Conference on Learning Theory, pages 3036–3083.
  * Wang et al., (2019) Wang, L., Cai, Q., Yang, Z., and Wang, Z. (2019).  Neural policy gradient methods: Global optimality and rates of convergence.  arXiv preprint arXiv:1909.01150.
  * Williams, (1992) Williams, R. J. (1992).  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine learning, 8(3-4):229–256.
  * Wu et al., (2020) Wu, Y., Zhang, W., Xu, P., and Gu, Q. (2020).  A finite time analysis of two time-scale actor critic methods.  arXiv preprint arXiv:2005.01350.
  * Xie et al., (2020) Xie, Q., Yang, Z., Wang, Z., and Minca, A. (2020).  Provable fictitious play for general mean-field games.  arXiv preprint arXiv:2010.04211.
  * (43) Xu, T., Liang, Y., and Lan, G. (2020a).  A primal approach to constrained policy optimization: Global optimality and finite-time analysis.  arXiv preprint arXiv:2011.05869.
  * (44) Xu, T., Wang, Z., and Liang, Y. (2020b).  Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms.  arXiv preprint arXiv:2005.03557.
  * Yang et al., (2020) Yang, W., Li, X., Xie, G., and Zhang, Z. (2020).  Finding the near optimal policy via adaptive reduced regularization in mdps.  arXiv preprint arXiv:2011.00213.
  * Zhan et al., (2021) Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, J. D., and Chi, Y. (2021).  Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence.  arXiv preprint arXiv:2105.11066.
  * (47) Zhang, J., Kim, J., O’Donoghue, B., and Boyd, S. (2020a).  Sample efficient reinforcement learning with REINFORCE.  arXiv preprint arXiv:2010.11364.
  * (48) Zhang, J., Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M. (2020b).  Variational policy gradient method for reinforcement learning with general utilities.  Advances in Neural Information Processing Systems, 33.
  * (49) Zhang, J., Ni, C., Yu, Z., Szepesvari, C., and Wang, M. (2021a).  On the convergence and sample efficiency of variance-reduced policy gradient method.  arXiv preprint arXiv:2102.08607.
  * Zhang et al., (2019) Zhang, K., Hu, B., and Basar, T. (2019).  Policy optimization for $\mathcal{H}_{2}$ linear control with $\mathcal{H}_{\infty}$ robustness guarantee: Implicit regularization and global convergence.  arXiv preprint arXiv:1910.09496.
  * (51) Zhang, K., Koppel, A., Zhu, H., and Basar, T. (2020c).  Global convergence of policy gradient methods to (almost) locally optimal policies.  SIAM Journal on Control and Optimization, 58(6):3586–3612.
  * (52) Zhang, X., Chen, Y., Zhu, X., and Sun, W. (2021b).  Robust policy gradient against strong data corruption.  arXiv preprint arXiv:2102.05800.
  * Zhao et al., (2021) Zhao, Y., Tian, Y., Lee, J., and Du, S. (2021).  Provably efficient policy gradient methods for two-player zero-sum Markov games.  arXiv preprint arXiv:2102.08903.


_Proof._ This is the contrapositive of point (ii) of Lemma 16. ∎

##  Appendix E The Tao matrix: uncertainty diagram, nonclassicality

We recall the Tao matrix [51] is the following unitary $6$ by $6$ matrix:

$U=\frac{1}{\sqrt{d}}\\\ \begin{pmatrix}1&1&1&1&1&1\\\
1&1&\omega&\omega&\omega^{2}&\omega^{2}\\\
1&\omega&1&\omega^{2}&\omega^{2}&\omega\\\
1&\omega&\omega^{2}&1&\omega&\omega^{2}\\\
1&\omega^{2}&\omega^{2}&\omega&1&\omega\\\
1&\omega^{2}&\omega&\omega^{2}&\omega&1\end{pmatrix},\quad\omega=\exp(i\frac{2\pi}{3}).$
(39)

Since all matrix elements have modulus $1/\sqrt{d}$, it can be viewed as the
transition matrix between two MUB. We will construct here the corresponding
uncertainty diagram. First, note that $U$ is certainly not COINC, since it
contains, for example, vanishing 2 minors, as is immediately seen.

We now first determine the uncertainty diagram of $U$, represented in Fig. 1.
Note that, if $(n_{{\mathcal{A}}},n_{{\mathcal{B}}})$ belongs to the
uncertainty diagram of a transition matrix $U$, then there exist
$S,T\subset\llbracket 1,d\rrbracket$ with
$|S|=n_{{\mathcal{A}}},|T|=n_{{\mathcal{B}}}$ and
${\mathcal{H}}(S,T)\not=\\{0\\}$. While this necessary condition is not
sufficient in general to conclude that $(n_{{\mathcal{A}}},n_{{\mathcal{B}}})$
belongs to the uncertainty diagram, a useful sufficient condition is given in
the following lemma.

######  Lemma 18.

Let $S,T\subset\llbracket 1,d\rrbracket$ and suppose
$\dim{\mathcal{H}}(S,T)=L\geq 1$. Suppose that for all $S^{\prime}\subset S$
for which $|S^{\prime}|=|S|-1$, one has $\dim{\mathcal{H}}(S^{\prime},T)\leq
L-1$, and that for all $T^{\prime}\subset T$ for which $|T^{\prime}|=|T|-1$,
one has $\dim{\mathcal{H}}(S,T^{\prime})\leq L-1$. Then the set of
$|\psi\rangle\in{\mathcal{H}}(S,T)$ for which
$n_{{\mathcal{A}}}(\psi)=|S|,n_{{\mathcal{B}}}(\psi)=|T|$ is an open and dense
set in ${\mathcal{H}}(S,T)$. The opposite implication is also true.

###### Proof.

For each $j\in S$, we have that ${\mathcal{H}}(S\setminus\\{j\\},T)$ is an at
most $L-1$-dimensional subspace of ${\mathcal{H}}(S,T)$. Hence the set
${\mathcal{H}}(S,T)\setminus{\mathcal{H}}(S\setminus\\{j\\},T)$ is open and
dense and this is true also for

$\cap_{j\in S}{\mathcal{H}}(S,T)\setminus{\mathcal{H}}(S\setminus\\{j\\},T).$

It is composed of all vectors $|\psi\rangle\in{\mathcal{H}}(S,T)$ for which
$n_{{\mathcal{A}}}(\psi)=|S|$. Similarly, the set of
$|\psi\rangle\in{\mathcal{H}}(S,T)$ for which $n_{{\mathcal{B}}}(\psi)=|T|$ is
open and dense as well. Taking the intersection, the direct implication
follows. To prove the opposite implication, one can work by contraposition.
Suppose there exist $S^{\prime}\subset S$ for which $|S^{\prime}|=|S|-1$, and
so that $\dim{\mathcal{H}}(S^{\prime},T)=L$. This of course means that
${\mathcal{H}}(S^{\prime},T)={\mathcal{H}}(S,T)$. Hence all states
$|\psi\rangle\in{\mathcal{H}}(S,T)$ have the property that $S_{\psi}\subset
S^{\prime}$ so that $n_{{\mathcal{A}}}(\psi)\leq|S^{\prime}|<|S|$. This
concludes the proof. ∎

We will use the above lemma repeatedly to determine the uncertainty diagram of
the Tao matrix. Note that, since the matrix is symmetric, so is the
uncertainty diagram. We first determine the dimension of ${\mathcal{H}}(S,T)$
in terms of $|S|$ and $|T|$.

One may first remark that,

$|S|+|T|\geq
7\quad\Rightarrow\quad\dim{\mathcal{H}}(S,T)=|S|-[6-|T||]=|S|+|T|-6.$ (40)

Indeed, if $|T|$ equals $1$ or $6$, this is immediate. Consider now the case
where $|T|\geq 2$ and $|S|=5$. Then we are imposing one constraint on the
$|T|$ components of $|\psi\rangle\in{\mathcal{H}}(T)$ on the
${\mathcal{B}}$-basis. Hence $\dim{\mathcal{H}}(S,T)=|T|-1=|S|+|T|-6$. To
proceed, we remark that a numerical computation shows that none of the 400
different $3\times 3$ minors of $U$ vanish. This implies that, when $|T|=3$
and $|S|=4$, the two constraints imposed on the three components of
$|\psi\rangle=d_{j_{1}}|b_{j_{1}}\rangle+d_{j_{2}}|b_{j_{2}}\rangle+d_{j_{3}}|b_{j_{3}}\rangle$
are necessarily independent so that $\dim{\mathcal{H}}(S,T)=3-2=1=|S|+|T|-6$.
Now consider the case where $|S|=4=|T|$. One then imposes two linearly
independent constraints on $4$ basis vectors. Hence
$\dim{\mathcal{H}}(S,T)=2=|S|+|T|-6$. Interchanging the roles of $S$ and $T$
in the previous arguments, (40) follows.

Next, we have that

$\displaystyle|S|+|T|=6,|T|\not=2\not=|S|$ $\displaystyle\Rightarrow$
$\displaystyle\dim{\mathcal{H}}(S,T)=0,$ (41) $\displaystyle|S|+|T|=6,|T|=2\
\mathrm{or}\ |S|=2$ $\displaystyle\Rightarrow$
$\displaystyle\dim{\mathcal{H}}(S,T)=0\ \textrm{or}\ 1.$ (42)

To see this, first remark that when $|S|=1$ or $|T|=1$, then this is immediate
since the basis vectors have full support. When $|S|=3=|T|$, the result
follows since all $3\times 3$ minors are nonvanishing. Consider the case
$|T|=2$ and $|S|=4$. With $T=\\{j_{1},j_{2}\\}$, one has
$|\psi\rangle=d_{j_{1}}|b_{j_{1}}\rangle+d_{j_{2}}|b_{j_{2}}\rangle$. If
$S^{c}=\\{i_{1},i_{2}\\}$, then $|\psi\rangle\in{\mathcal{H}}(S,T)$ provided
$\langle a_{i_{1}}|\psi\rangle=0=\langle a_{i_{2}}|\psi\rangle$. Inspecting
the matrix $U$ one observes that two such constraints can be either linearly
dependent or independent, depending on the choice of
$i_{1},i_{2},j_{1},j_{2}$. So $\dim{\mathcal{H}}(S,T)=1$ or $0$. The same is
true with the roles of $S$ and $T$ interchanged, proving (41)-(42).

Finally, one has

$|S|+|T|\leq 5\Rightarrow\dim{\mathcal{H}}(S,T)=0.$ (43)

Since $\dim{\mathcal{H}}(S,T)$ is a nondecreasing function of $|S|$ and of
$|T|$, this follows from what precedes.

We now use Lemma 18 to conclude. First, if
$n_{{\mathcal{A}}}+n_{{\mathcal{B}}}\geq 8$, Eq. (40) allows us to conclude
that $(n_{{\mathcal{A}}},n_{{\mathcal{B}}})$ belongs to the uncertainty
diagram. Next, when $n_{{\mathcal{A}}}+n_{{\mathcal{B}}}\leq 5$, Eq. (43)
implies $(n_{{\mathcal{A}}},n_{{\mathcal{B}}})$ does not belong to the
uncertainty diagram. Consider then the case where
$n_{{\mathcal{A}}}+n_{{\mathcal{B}}}=6$. Clearly $(1,5),(3,3),(5,1)$ do not
belong to the uncertainty diagram because for these cases
$\dim{\mathcal{H}}(S,T)=\\{0\\}$. Since there exist $S,T$ with $|S|=2,|T|=4$
for which $\dim{\mathcal{H}}(S,T)=1$, it follows from Eq. (43) and Lemma 18
that $(2,4)$ does belong to the uncertainty diagram.

It remains to check the case where $n_{{\mathcal{A}}}+n_{{\mathcal{B}}}=7$. We
know $(1,6)$ and $(6,1)$ do belong to the uncertainty diagram. An inspection
of the Tao matrix shows that $(2,5)$ and $(5,2)$ do not belong to the
uncertainty diagram. For the state

$|\psi\rangle=\omega|b_{1}\rangle-(1+\omega)|b_{2}\rangle+|b_{3}\rangle$

one sees readily that
$(n_{{\mathcal{A}}}(\psi),n_{{\mathcal{B}}}(\psi))=(4,3)$.

In conclusion, the uncertainty diagram of the Tao matrix is includes all
$(n_{{\mathcal{A}}},n_{{\mathcal{B}}})$ for which
$n_{{\mathcal{A}}}+n_{{\mathcal{B}}}\geq 7$, except for $(2,5),(5,2)$, as well
as the points $(2,4)$ and $(4,2)$. In particular, the lower edge
$L(n_{{\mathcal{A}}})$ of the diagram is given by

$L(1)=6,\quad L(2)=4,\quad L(3)=4,\quad L(4)=2,\quad L(5)=3,\quad L(6)=1.$

It remains to discuss the KD (non)classicality of the states in function of
their support uncertainty. We know from Proposition 11 that all states
$|\psi\rangle$ with $n_{{\mathcal{A}}}(\psi)+n_{{\mathcal{B}}}(\psi)>7$ are
KDNC. These are indicated with (blue) diamonds in Fig. 1. When
$n_{{\mathcal{A}}}(\psi)+n_{{\mathcal{B}}}(\psi)\leq 7$, the basis states for
which $(n_{{\mathcal{A}}}(\psi),n_{{\mathcal{B}}}(\psi)=(6,1)$ or $(1,6)$ are
all classical. They are indicated as (red) squares in Fig. 1. We have verified
with a numerical computation that, when
$(n_{{\mathcal{A}}}(\psi),n_{{\mathcal{B}}}(\psi))=(3,4)$, $(4,3)$, $(2,4)$ or
$(4,2)$, $|\psi\rangle$ is KD nonclassical.

##  Appendix F COINCs are an open dense set

We will prove Theorem 5 and Theorem 10 here; they are immediate consequences
of Theorem 20 below. The proof relies crucially on Lemma 6 that was shown in
[19]. We give, for completeness, a slightly different proof of it, in the
following Lemma.

######  Lemma 19.

(i) Let $1\leq|S|<d,1\leq|T|\leq d$. Then Rank $U(S^{c},T)<|T|$ if and only if
${\Pi_{{\mathcal{A}}}}(S){\mathcal{H}}\cap{\Pi_{{\mathcal{B}}}}(T){\mathcal{H}}\not=\\{0\\}$.
(ii) Let $1\leq|S|<d,1\leq|T|\leq d$. Then Rank $U(S^{c},T)=|T|$ if and only
if ${\Pi_{{\mathcal{A}}}}(S)\cap{\Pi_{{\mathcal{B}}}}(T)=\\{0\\}$.
(iii) Let $1\leq|T|<d$ and let $S$ be such that $|S|=d-|T|$. Then det
$U(S^{c},T)\not=0$ if and only if
${\Pi_{{\mathcal{A}}}}(S)\cap{\Pi_{{\mathcal{B}}}}(T)=\\{0\\}$.
(iv) ${\mathcal{A}}$ and ${\mathcal{B}}$ are COINC if and only if none of the
minors of the matrix $U$ vanish.

###### Proof.

(i) Reordering the bases ${\mathcal{A}},{\mathcal{B}}$, we can assume
$S^{c}=\llbracket 1,K\rrbracket$, with $K=|S^{c}|$ and $T=\llbracket
1,L\rrbracket$ with $L=|T|$. Hence

$U(S^{c},T)=\begin{pmatrix}\langle a_{1}|b_{1}\rangle&\dots&\langle
a_{1}|b_{L}\rangle\\\ \vdots&\vdots&\vdots\\\ \langle
a_{K}|b_{1}\rangle&\dots&\langle a_{K}|b_{L}\rangle\end{pmatrix}.$

Consequently, one has that
$|\psi\rangle=\sum_{j=1}^{L}\beta_{j}|b_{j}\rangle\in{\Pi_{{\mathcal{A}}}}(S){\mathcal{H}}\cap{\Pi_{{\mathcal{B}}}}(T){\mathcal{H}}$
if and only if $\beta=(\beta_{1},\dots,\beta_{K})^{T}\in\textrm{Ker}\
U(S^{c},T)$.
_Proof of_ $\Rightarrow$. Since

$\textrm{Rank}U(S^{c},T)+\textrm{Ker}U(S^{c},T)=L=|T|,$

it follows from the hypothesis that Ker $U(S^{c},T)=\\{0\\}$, which implies
the result.
_Proof of_ $\Leftarrow$. Let
$0\not=\psi=\sum_{j=1}^{L}\beta_{j}|b_{j}\rangle\in{\Pi_{{\mathcal{A}}}}(S){\mathcal{H}}\cap{\Pi_{{\mathcal{B}}}}(T){\mathcal{H}}$.
Then $U(S^{c},T)\beta=0$ so that Ker $U(S^{c},T)\not=\\{0\\}$. Hence
$\textrm{Rank}\ U(S,T)<|T|$.
(ii) This is the contraposition of (i).
(iii) This follows directly from (ii) since now the matrix $U(S^{c},T)$ is a
square matrix.
(iv) Note that all minors of $U$ are determinants of matrices of the form
$U(S^{c},T)$, with $|S^{c}|=|T|$ and hence $|S|=d-|T|$. Now suppose
${\mathcal{A}}$ and ${\mathcal{B}}$ are COINC. Then, for any such $S,T$,
${\Pi_{{\mathcal{A}}}}(S)\cap{\Pi_{{\mathcal{B}}}}(T)=\\{0\\}$. Hence (iii)
implies the determinant of $U(S^{c},T)$ does not vanish. It remains to prove
the converse. Suppose therefore that, whenever $|S|+|T|=d$, det
$U(S^{c},T)\not=0$. Then, according to (iii),
${\Pi_{{\mathcal{A}}}}(S){\mathcal{H}}\cap{\Pi_{{\mathcal{B}}}}(T){\mathcal{H}}=\\{0\\}$.
Now, suppose $S^{\prime}\subset S,T^{\prime}\subset T$, then we still have
${\Pi_{{\mathcal{A}}}}(S^{\prime}){\mathcal{H}}\cap{\Pi_{{\mathcal{B}}}}(T^{\prime}){\mathcal{H}}=\\{0\\}$.
This concludes the proof. ∎

To state Theorem 20, we need some preliminaries. Let
${\mathcal{A}}=(|a_{1}\rangle,|a_{2}\rangle,\dots,|a_{d}\rangle)$ and
${\mathcal{B}}=(|b_{1}\rangle,|b_{2}\rangle,\dots,|b_{d}\rangle)$ be two
orthonormal bases in ${\mathcal{H}}$, with transition matrix $U$ and suppose
$V,W$ are unitary $d\times d$ matrices. Then we construct the orthonormal
bases
${\mathcal{A}}^{\prime}=(|a^{\prime}_{1}\rangle,\dots,|a^{\prime}_{d}\rangle)$,
${\mathcal{B}}^{\prime}=(|b_{1}^{\prime}\rangle,\dots,|b_{d}^{\prime}\rangle)$
by

$|a_{i}^{\prime}\rangle=\sum_{j}V_{ji}|a_{j}\rangle,\quad|b^{\prime}_{j}\rangle=\sum_{k}W_{kj}|b_{k}\rangle.$

We will write
${\mathcal{A}}^{\prime}={\mathcal{A}}V,\quad{\mathcal{B}}^{\prime}={\mathcal{B}}W.$
Their transition matrix $U^{\prime}$ is

$U^{\prime}=V^{\dagger}UW.$

Note that, since $|b_{i}\rangle=\sum_{j}U_{ji}|a_{j}\rangle$, we have
${\mathcal{B}}={\mathcal{A}}U$. Let $\sigma$ be a permutation of $\llbracket
1,d\rrbracket$. Let $P_{\sigma}=(e_{\sigma_{1}}\dots e_{\sigma_{d}})$ where
$e_{1},\dots,e_{d}$ is the canonical basis of $\mathbb{C}^{d}$. Then
${\mathcal{A}}P_{\sigma}=(|a_{\sigma_{1}}\rangle,\dots,|a_{\sigma_{d}}\rangle)$.
Remark for further computations that, for all $d^{\prime}\times d$ matrices
$C=(c_{1}\dots c_{d})$, and all $d\times d^{\prime}$ matrices
$F=\begin{pmatrix}f_{1}\\\ \vdots\\\ f_{d}\end{pmatrix}$,

$P_{\sigma}P_{\tau}=P_{(\sigma\circ\tau)},\quad
P_{\sigma}^{T}=P_{\sigma}^{\dagger}=P_{\sigma^{-1}},\quad
CP_{\sigma}=(c_{\sigma_{1}}\dots c_{\sigma_{d}}),\quad
P_{\sigma}F=\begin{pmatrix}f_{\sigma_{1}^{-1}}\\\ \vdots\\\
f_{\sigma_{d}^{-1}}\end{pmatrix}.$

It follows from the above that, if $U$ is the transition matrix for two bases
${\mathcal{A}}$ and ${\mathcal{B}}$, and if
${\mathcal{A}}^{\prime}={\mathcal{A}}P_{\sigma},{\mathcal{B}}^{\prime}={\mathcal{B}}P_{\tau}$,
then the transition matrix $U^{\prime}$ for ${\mathcal{A}}^{\prime}$ and
${\mathcal{B}}^{\prime}$ is

$U^{\prime}=P_{\sigma^{-1}}UP_{\tau},$ (44)

since

$\displaystyle U^{\prime}_{ij}$ $\displaystyle=$ $\displaystyle\langle
a^{\prime}_{i}|b^{\prime}_{j}\rangle=\langle
a_{\sigma_{i}}|b_{\tau_{j}}\rangle=U_{\sigma_{i}\tau_{j}}$ $\displaystyle=$
$\displaystyle\langle
e_{\sigma_{i}},Ue_{\tau_{j}}\rangle_{\mathbb{C}^{d}}=\langle
P_{\sigma}e_{i},UP_{\tau}e_{j}\rangle_{\mathbb{C}^{d}}$ $\displaystyle=$
$\displaystyle\langle
e_{i},P_{\sigma}^{\dagger}UP_{\tau}e_{j}\rangle_{\mathbb{C}^{d}},$

where $\langle\cdot,\cdot\rangle_{\mathbb{C}^{d}}$ is the inner product on
$\mathbb{C}^{d}$. Note that $U^{\prime}$ is obtained from $U$ by permuting its
rows by $\sigma$ and its columns by $\tau$. The central result of this
Appendix is then the following theorem.

######  Theorem 20.

Let ${\mathcal{A}}$, ${\mathcal{B}}$ be orthonormal bases in ${\mathcal{H}}$,
with transition matrix $U$. Then there exists a family of unitary matrices
$T(\epsilon)$ with $\epsilon>0$, and $\lim_{\epsilon\to
0}T(\epsilon)=\mathbb{I}_{d}$, and so that the bases
${\mathcal{A}}(\epsilon)={\mathcal{A}}T(\epsilon)^{\dagger}$ and
${\mathcal{B}}$ are COINC for all sufficiently small $\epsilon$. One has
${\mathcal{B}}={\mathcal{A}}(\epsilon)U(\epsilon)$, with
$U(\epsilon)=T(\epsilon)U$.

###### Proof.

We will construct $T(\epsilon)$ recursively. Note first that, by Lemma 6, if
$U$ has no vanishing minors, then the result holds and we can simply put
$T(\epsilon)=\mathbb{I}_{d}$. We therefore suppose that $U$ does have at least
one vanishing minor. We will perform a “downward” recursion on the number of
vanishing minors of $U$.

Consider therefore an arbitrary unitary $d\times d$ matrix $U$ and let $1\leq
L$ be the number of vanishing minors of $U$. Let $M_{i}$, $i=1,\dots,L$ be the
list of the corresponding $\ell_{i}\times\ell_{i}$ submatrices of $U$; $\det
M_{i}=0$. Since $U$ is unitary, we know $\ell_{i}<d$. We can order the $M_{i}$
so that $d>\ell_{1}\geq\ell_{2}\geq\dots\geq\ell_{L}$. Let $\sigma_{1}$,
respectively $\tau_{1}$, be permutations that send the columns and rows of
$M_{1}$ to $1,2,3,\dots\ell_{1}$. Then, the $\ell_{1}$-minor of

$U^{\prime}=P_{\sigma_{1}}^{\dagger}UP_{\tau_{1}}$

corresponding to its first $\ell_{1}$ rows and columns vanishes, whereas the
$k_{1}=\ell_{1}+1$-minor corresponding to its $k_{1}$ first rows and columns
does not. Indeed, since $U^{\prime}$ is obtained from $U$ by permuting its
columns and rows, the number of vanishing minors of $U^{\prime}$ is equal to
that of $U$ and the maximal dimension of those minors is still $\ell_{1}<d$.
Writing $M_{1}^{\prime+}$ for this $k_{1}\times k_{1}$ submatrix, we are now
in the situation of Lemma 21 since, by the above, $\det
M_{1}^{\prime+}\not=0$. There therefore exists a continuous family
$V_{1}(\theta_{1})$ of unitary $k_{1}$ by $k_{1}$ matrices so that
$M_{1}^{\prime+}(\theta_{1})=V_{1}(\theta_{1})M_{1}^{\prime+}$ has the
property that, there exists $\theta_{1}^{*}>0$ so that for all
$0<\theta_{1}\leq\theta_{1}^{*}$, $\det M_{1}^{\prime+}(\theta_{1})\not=0$ and
$\det M_{1}^{\prime}(\theta_{1})\not=0$. We can then construct the continuous
family of unitary $d\times d$ matrices

$T_{1}(\theta_{1})=\begin{pmatrix}V_{1}(\theta_{1})&0\\\
0&\mathbb{I}_{d-k_{1}}\end{pmatrix},\quad T_{1}(0)=\mathbb{I}_{d}.$

Then $M_{1}^{\prime}(\theta_{1})$ is the submatrix of
$U^{\prime}(\theta_{1})=T_{1}(\theta_{1})P_{\sigma_{1}}^{\dagger}UP_{\tau_{1}}$
containing its first $\ell_{1}$ columns and rows. Its determinant does not
vanish. Since for small $\theta_{1}$, $V_{1}(\theta_{1})$ is close to the
identity, all non-vanishing minors of $U^{\prime}$ are non-vanishing minors of
$U^{\prime}(\theta_{1})$; therefore the number of nonvanishing minors of
$U^{\prime}(\theta_{1})$ has increased by at least one. Hence, the number of
vanishing minors of $U^{\prime}(\theta_{1})$ is at most equal to $L-1$
provided $\theta_{1}$ is small enough and different from $0$. The same is then
true for
$P_{\sigma_{1}}U^{\prime}(\theta_{1})P_{\tau_{1}}^{\dagger}=P_{\sigma_{1}}T_{1}(\theta_{1})P_{\sigma_{1}}^{\dagger}U$.

Now, let $0<\epsilon<\theta_{1}^{*}$ and set $\theta_{1}=\epsilon$. Then
$U_{1}(\epsilon):=P_{\sigma_{1}}T_{1}(\epsilon)P_{\sigma_{1}}^{\dagger}U$ has
at most $L_{\epsilon,1}\leq L-1$ vanishing minors. We can then repeat the
process. There exists $\theta_{2}^{*}$, $\sigma_{2},\tau_{2}$ and for all
$0<\theta_{2}<\theta_{2}^{*}$, $T_{2}(\theta_{2})$, constructed as above, so
that $P_{\sigma_{2}}T_{2}(\theta_{2})P_{\sigma_{2}}^{\dagger}U_{1}(\epsilon)$
has at most $L_{\epsilon,1}-1$ vanishing minors. Note that $\theta_{2}^{*}$,
$\sigma_{2},\tau_{2}$ all depend on $\epsilon$: we did not indicate this
dependence, not to overly burden the notation. But it is important to keep it
in mind. We now define
$\theta_{2}(\epsilon)=\min\\{\epsilon,\theta_{2}^{*}\\}$ and
$U_{2}(\epsilon)=P_{\sigma_{2}}T_{2}(\theta_{2}(\epsilon))P_{\sigma_{2}}^{\dagger}U_{1}(\epsilon)$.
Then $U_{2}(\epsilon)$ has at most $L_{\epsilon,2}\leq L-2$ vanishing minors.

Repeating this process at most $L^{\prime}_{\epsilon}\leq L$ times, we
conclude that there exist permutations $\sigma_{j}$ and unitary maps
$T_{j}(\theta_{j}(\epsilon))$ with $0<\theta_{j}(\epsilon)\leq\epsilon$ so
that,

$T(\epsilon)U:=\Pi_{j=L^{\prime}_{\epsilon}}^{1}P_{\sigma_{j}}T_{j}(\theta_{j}(\epsilon))P_{\sigma_{j}}^{\dagger}U$

has no vanishing minors. By construction, $\lim_{\epsilon\to 0}T(\epsilon)=0$.
Defining ${\mathcal{A}}(\epsilon)={\mathcal{A}}T^{\dagger}(\epsilon)$, we have
${\mathcal{B}}={\mathcal{A}}U={\mathcal{A}}(\epsilon)T(\epsilon)U$. Since, by
the above, $T(\epsilon)U$ has no vanishing minors, provided $\epsilon$ is
small enough, the result follows from Lemma 6. ∎

The central argument of the above proof is contained in the technical Lemma 21
below. To state and prove it, we need some further notation. Let
$M^{+}=(m_{1}^{+}\dots m_{k}^{+})$ be a $k\times k$ matrix, with columns
$m_{i}^{+}\in\mathbb{C}^{k}$:

$m_{i}^{+}=\begin{pmatrix}m_{i}\\\ \overline{\mu}_{i}\end{pmatrix},$

with $m_{i}\in\mathbb{C}^{\ell}$ with $\ell=k-1$ and $\mu_{i}\in\mathbb{C}$.
We introduce the $\ell\times\ell$ matrix $M=(m_{1}\dots m_{\ell})$ as well as

$\mu=\begin{pmatrix}\mu_{1}\\\ \vdots\\\
\mu_{\ell}\end{pmatrix}\in\mathbb{C}^{\ell}.$

So we have

$M^{+}=\left(\begin{array}[]{c|c}M&m_{k}\\\
\hline\cr\mu^{\dagger}&\overline{\mu}_{k}\end{array}\right).$

Here, for any $v\in\mathbb{C}^{\ell}$, $v^{\dagger}$ is its conjugate
transpose. We will write Ker$M$ for the null space of $M$, meaning those
$x\in\mathbb{C}^{\ell}$ for which $Mx=0$; and ${\mathrm{Im}}M$ for the image
of $M$, which is its column space. Also, if $v\in\mathbb{C}^{\ell}$ is a
vector, $\mathbb{C}v$ is the complex line containing $v$ and
$[\mathbb{C}v]^{\perp}$ is the vector subspace of $\mathbb{C}^{\ell}$ that is
perpendicular to it. If $v\not=0$, this is a $(\ell-1)$-dimensional
hyperplane.

######  Lemma 21.

Let $k\geq 2$. If $\det M^{+}\not=0$ and $\det M=0$, then $\mu\not=0$ and

  * (i)

${\mathrm{Ker}}M\cap[\mathbb{C}\mu^{\dagger}]^{\perp}=\\{0\\}$;

  * (ii)

${\mathrm{Ker}}M$ is one-dimensional and ${\mathrm{Im}}M$ is
$(\ell-1)=(k-2)$-dimensional.

In addition, there exists a one-parameter continuous family of unitary $k$ by
$k$ matrices $V(\theta)$, $\theta\in[-\pi,\pi]$, with $V(0)=\mathbb{I}_{k}$ so
that, defining $M^{+}(\theta)=V(\theta)M^{+}=(m_{1}^{+}(\theta)\dots
m_{k}^{+}(\theta))$, one has $\det M^{+}(\theta)\not=0\not=\det M(\theta)$,
for all small enough $\theta\not=0$.

Recall that the rank of a matrix is the maximal number of linearly independent
columns. Since $M^{+}$ is invertible, it has maximal rank $k$. Since the
determinant of $M$ vanishes, its rank is strictly less than $\ell$. The
important information in the second statement of the Lemma is therefore that
the rank of $M$ equals $\ell-1$. The last statement asserts that a small
unitary perturbation of the matrix $M^{+}$ suffices to make $M$ invertible.

To follow the proof it is convenient to have a low dimensional example in
mind. For $k=3$, $\ell=2$, the following matrix $M^{+}$ satisfies the
hypotheses of the theorem

$M^{+}=\begin{pmatrix}1&2&1\\\ 1&2&2\\\
3&-1&3\end{pmatrix},\quad\mu=\begin{pmatrix}3\\\ -1\end{pmatrix},\
[\mathbb{C}\mu^{\dagger}]^{\perp}=\begin{pmatrix}1\\\ 3\end{pmatrix},\
{\mathrm{Ker}}M=\mathbb{C}\begin{pmatrix}2\\\ -1\end{pmatrix},\
{\mathrm{Im}}M=\mathbb{C}\begin{pmatrix}1\\\ 1\end{pmatrix}.$

The first two assertions of the Lemma are now clearly satisfied. In the proof,
we will construct $V(\theta)$ to be the rotation over an angle $\theta$ in the
plane spanned by $e_{3}$ and

$b^{+}=\begin{pmatrix}b\\\
0\end{pmatrix}=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\\ -1\\\ 0\end{pmatrix},$

where $b$ is chosen orthogonal to ${\mathrm{Im}}M$. It is clear in this
example that such rotations will tilt the plane spanned by $m_{1}^{+}$ and
$m_{2}^{+}$ into the plane spanned by $m_{1}^{+}(\theta)=V(\theta)m_{1}^{+}$
and $m_{2}^{+}(\theta)=V(\theta)m_{2}^{+}$ in such a way that their
projections $m_{1}(\theta)$ and $m_{2}(\theta)$ onto the $e_{1}-e_{2}$ plane
are no longer aligned. Hence the determinant of $M(\theta)$ does not vanish.
This argument works in general, as we now show.

###### Proof.

Note first that, if $\mu=0$, then $\det M^{+}=\overline{\mu}_{k}\det M$ which
is in contradiction with the hypothesis. So $\mu\not=0$.

We now prove that (i) implies (ii). From the dimension theorem for sums of
vector spaces, we know that

$\dim({\mathrm{Ker}}M+[\mathbb{C}\mu^{\dagger}]^{\perp})=\dim{\mathrm{Ker}}M+\dim[\mathbb{C}\mu^{\dagger}]^{\perp}-\dim({\mathrm{Ker}}M\cap[\mathbb{C}\mu^{\dagger}]^{\perp})$

Now, ${\mathrm{Ker}}M+[\mathbb{C}\mu^{\dagger}]^{\perp}$ is by definition the
linear span of ${\mathrm{Ker}}M$ and $[\mathbb{C}\mu^{\dagger}]^{\perp}$ and
is therefore a subspace of $\mathbb{C}^{\ell}$, so that
$\dim({\mathrm{Ker}}M+[\mathbb{C}\mu^{\dagger}]^{\perp})\leq\ell$. Hence (i)
implies that

$\dim{\mathrm{Ker}}M+\dim[\mathbb{C}\mu^{\dagger}]^{\perp}\leq\ell.$

Since $\mu\not=0$, we know that $\dim[\mathbb{C}\mu^{\dagger}]^{\perp}=\ell-1$
and consequently $\dim{\mathrm{Ker}}M\leq 1$. But by assumption $\det M=0$, so
$M$ has a non-trivial kernel. Hence $\dim{\mathrm{Ker}}M=1$. From the
dimension theorem for linear maps, we know that

$\dim{\mathrm{Ker}}M+\dim\textrm{Im}M=\ell,$

so that $\dim\textrm{Im}M=\ell-1$, which proves (ii).

It remains to prove (i). For that purpose, note that

$m_{i}^{+}=m_{i}+\overline{\mu_{i}}e_{k},\quad\textrm{where}\
e_{k}=\begin{pmatrix}0\\\ \vdots\\\ 1\end{pmatrix}\in\mathbb{C}^{k}.$

Hence, for all $z\in\mathbb{C}^{\ell}$, one has

$\sum_{i=1}^{\ell}z_{i}m_{i}^{+}=\sum_{i=1}^{\ell}z_{i}m_{i}+(\mu^{\dagger}z)e_{k}.$

Suppose $z\in[\mathbb{C}\mu]^{\perp}\cap{\mathrm{Ker}}M$. Then the right hand
side vanishes; but since the $m_{i}^{+}$ are linearly independent, this
implies all $z_{i}=0$. This proves the result.

We now turn to the last statement of the Lemma.

Under the conditions of the Lemma,
$[{\mathrm{Im}}M]^{\perp}\subset\mathbb{C}^{\ell}$ is one-dimensional. Let
$b\in{\mathrm{Im}}M^{\perp}$ be a unit vector: $b^{\dagger}b=1$. Let
$b^{+}=\begin{pmatrix}b\\\ 0\end{pmatrix}$ and let $\Pi$ be the orthogonal
projector onto the plane spanned by $b^{+}$ and $e_{k}$:

$\Pi=b^{+}b^{+\dagger}+e_{k}e_{k}^{\dagger}\quad\textrm{and}\quad\Pi^{\perp}=\mathbb{I}_{k}-\Pi.$

Note that $\Pi^{\perp}$ is the orthogonal projector onto the image of $M$
(viewed as a subspace of $\mathbb{C}^{k}$, not of $\mathbb{C}^{\ell}$). Now
consider, for all $\theta\in[0,2\pi[$,

$V(\theta)=R(\theta)\Pi+\Pi^{\perp},$

where $R(\theta)$ is a rotation in the plane spanned by $b^{+}$ and $e_{k}$:

$R(\theta)=\cos\theta\Pi+\sin\theta\left(e_{k}b^{+\dagger}-b^{+}e_{k}^{\dagger}\right).$

One easily checks $V(\theta)$ is unitary, continuous in $\theta$ and that
$V(0)=\mathbb{I}_{k}$.

We now consider

$M^{+}(\theta)=V(\theta)M^{+}=(m_{1}^{+}(\theta)\dots
m_{k}^{+}(\theta)),\quad\textrm{and}\quad
m_{i}^{+}(\theta)=\begin{pmatrix}m_{i}(\theta)\\\
\mu_{i}(\theta)\end{pmatrix}.$

Since, for all $i=1,\dots,\ell$, $\Pi m_{i}=0$ by the above construction, a
direct computation yields,

$m_{i}^{+}(\theta)=V(\theta)m_{i}^{+}=m_{i}+\overline{\mu}_{i}R(\theta)e_{k}=m_{i}+\overline{\mu}_{i}[\cos\theta
e_{k}-\sin\theta b^{+}]$

and hence

$m_{i}(\theta)=m_{i}-\overline{\mu}_{i}\sin\theta
b,\quad\mu_{i}(\theta)=\mu_{i}\cos\theta.$

It remains to show that $\det M(\theta)\not=0\not=\det M^{+}(\theta)$ for all
$\theta$ small enough. To show $\det M(\theta)\not=0$ we need to show the
vectors $m_{i}(\theta)$ are linearly independent. Let $0<\theta<\pi$. Consider
$z_{i}\in\mathbb{C}$, $i=1,\dots,\ell$ and suppose that

$\sum_{i=1}^{\ell}z_{i}m_{i}(\theta)=0.$

Then

$0=\sum_{i=1}^{\ell}z_{i}m_{i}-(\sum_{i=1}^{\ell}\overline{\mu}_{i}z_{i})\sin\theta
b.$

Since $b$ is orthogonal to all $m_{i}$, this implies $z\in{\mathrm{Ker}}M$ and
$z\in[\mathbb{C}\mu^{\dagger}]^{\perp}$. Hence by part (i) of the lemma we
conclude $z_{i}=0$ for all $i=1,\dots,\ell$, so that the vectors
$m_{i}(\theta)$ are indeed linearly independent.

Since $\det M^{+}\not=0$, this remains true, by continuity, for $\det
M^{+}(\theta)$ for $\theta$ small enough.

∎

##  Appendix G KD nonclassicality in dimension $d=3$

It is a simple matter to check that, when $d=3$, Theorems 12 and 15 are in
fact equivalent. First, note that both theorems require
$M_{{\mathcal{A}},{\mathcal{B}}}<1$. Next, when $d=3$, $3d/2=4.5$ and hence
the sufficient condition on $|\psi\rangle$ for KD nonclassicality in Theorem
15 is $n_{\mathcal{A}}(\psi)+n_{\mathcal{B}}(\psi)\geq 5$. While in Theorem 12
it is $n_{{\mathcal{A}}}(\psi)+n_{{\mathcal{B}}}(\psi)>d+1=4$, which is the
same condition. It remains to show that the additional conditions on the
number of zeros of $U$ in Theorem 12 are in fact always satisfied. For that
purpose we show that the possible values for $Z$ are $Z=0,1$. In other words,
the condition $Z\leq\frac{d+1}{2}=2$ is in fact not restrictive. Indeed,
suppose $Z\geq 2$. One easily sees that two zeros cannot occur in the same row
or column because then necessarily $M_{{\mathcal{A}},{\mathcal{B}}}=1$. The
matrix is therefore (after possible permutations of columns or rows) of the
form

$U=\begin{pmatrix}0&\cdot&\cdot\\\ \cdot&0&\cdot\\\ x&y&\cdot\end{pmatrix}.$

Unitarity then implies $\overline{x}y=0$ and hence either $x=0$ or $y=0$, so
that there is a third zero, which occurs in one of the first two columns. But
this is impossible since $M_{{\mathcal{A}},{\mathcal{B}}}<1$.

## References

  * [1] Lars M. Johansen.  Quantum theory of successive projective measurements.  Phys. Rev. A, 76:012119, Jul 2007.
  * [2] Robert W. Spekkens.  Negativity and contextuality are equivalent notions of nonclassicality.  Phys. Rev. Lett., 101:020401, Jul 2008.
  * [3] Teiko Heinosaari and Michael M. Wolf.  Nondisturbing quantum measurements.  Journal of Mathematical Physics, 51(9):092201, 2010.
  * [4] Matthew F. Pusey.  Anomalous weak values are proofs of contextuality.  Phys. Rev. Lett., 113:200401, Nov 2014.
  * [5] Justin Dressel.  Weak values as interference phenomena.  Phys. Rev. A, 91:032116, Mar 2015.
  * [6] Teiko Heinosaari, Takayuki Miyadera, and Mário Ziman.  An invitation to quantum incompatibility.  Journal of Physics A: Mathematical and Theoretical, 49(12):123001, feb 2016.
  * [7] Nicole Yunger Halpern, Brian Swingle, and Justin Dressel.  Quasiprobability behind the out-of-time-ordered correlator.  Phys. Rev. A, 97:042105, Apr 2018.
  * [8] Matteo Lostaglio.  Quantum fluctuation theorems, contextuality, and work quasiprobabilities.  Phys. Rev. Lett., 120:040602, Jan 2018.
  * [9] Claudio Carmeli, Teiko Heinosaari, and Alessandro Toigo.  Quantum random access codes and incompatibility of measurements.  Europhysics Letters, 130(5):50001, 2020.
  * [10] Roope Uola, Tristan Kraft, Sébastien Designolle, Nikolai Miklin, Armin Tavakoli, Juha-Pekka Pellonpää, Otfried Gühne, and Nicolas Brunner.  Quantum measurement incompatibility in subspaces.  Phys. Rev. A, 103:022203, Feb 2021.
  * [11] Christopher Ferrie.  Quasi-probability representations of quantum theory with applications to quantum information science.  Rep. Prog. Phys., 74:116001, 2011.
  * [12] Jeff S. Lundeen and Charles Bamber.  Procedure for direct measurement of general quantum states using weak measurement.  Phys. Rev. Lett., 108:070402, Feb 2012.
  * [13] Charles Bamber and Jeff S. Lundeen.  Observing Dirac’s Classical Phase Space Analog to the Quantum State.  Phys. Rev. Lett., 112:070405, Feb 2014.
  * [14] G. S. Thekkadath, L. Giner, Y. Chalich, M. J. Horton, J. Banker, and J. S. Lundeen.  Direct measurement of the density matrix of a quantum system.  Phys. Rev. Lett., 117:120401, Sep 2016.
  * [15] David R. M. Arvidsson-Shukur, Nicole Yunger Halpern, Hugo V. Lepage, Aleksander A. Lasek, Crispin H. W. Barnes, and Seth Lloyd.  Quantum advantage in postselected metrology.  Nature Communications, 11(1):3775, 2020.
  * [16] David R. M. Arvidsson-Shukur, Jacob Chevalier Drori, and Nicole Yunger Halpern.  Conditions tighter than noncommutation needed for nonclassicality.  J. Phys. A, 54(28):Paper No. 284001, 20, 2021.
  * [17] Sébastien Designolle, Máté Farkas, and Jedrzej Kaniewski.  Incompatibility robustness of quantum measurements: a unified framework.  New Journal of Physics, 21(11):113053, nov 2019.
  * [18] Krzysztof Mordasewicz and Jedrzej Kaniewski.  Quantifying incompatibility of quantum measurements through non-commutativity, 2021.
  * [19] Stephan De Bièvre.  Complete incompatibility, support uncertainty, and kirkwood-dirac nonclassicality.  Phys. Rev. Lett., 127:190404, Nov 2021.
  * [20] Julian Schwinger.  Unitary operator bases.  Proc. Nat. Acad. Sci. U.S.A., 46:570–579, 1960.
  * [21] I D Ivonovic.  Geometrical description of quantal state determination.  Journal of Physics A: Mathematical and General, 14(12):3241–3245, dec 1981.
  * [22] Michel Planat, Haret C. Rosu, and Serge Perrine.  A survey of finite algebraic geometrical structures underlying mutually unbiased quantum measurements.  Found. Phys., 36(11):1662–1680, 2006.
  * [23] T. Durt, B.-G. Englert, I Bengtsson, and K Zyczkowski.  On mutually unbiased bases.  Int. J. Quantum Inf., pages 535–640, 2010.
  * [24] Máté Farkas and Jedrzej Kaniewski.  Self-testing mutually unbiased bases in the prepare-and-measure scenario.  Phys. Rev. A, 99:032316, Mar 2019.
  * [25] Teo Banica.  Complex hadamard matrices and applications.  arXiv:1910.06911, 2022.
  * [26] John G. Kirkwood.  Quantum statistics of almost classical assemblies.  Phys. Rev., 44:31–37, Jul 1933.
  * [27] P. A. M. Dirac.  On the analogy between classical and quantum mechanics.  Rev. Mod. Phys., 17:195–199, Apr 1945.
  * [28] K. Cahill and R. J. Glauber.  Ordered expansions in boson amplitude operators.  Phys. Rev., 177:1857, 1969.
  * [29] K. Cahill and R. J. Glauber.  Density operators and quasi-probability distributions.  Phys. Rev., 177:1882, 1969.
  * [30] Michael A. Nielsen and Isaac L Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2010.
  * [31] Cohen-Tannoudji Claude, Diu Bernard, and Laloë Franck.  Quantum Mechanics, volume 1.  Wiley, 2015.
  * [32] G. Lüders.  Ann. Physik, page 322, 1951.
  * [33] Gerald B. Folland and Alladi Sitaram.  The uncertainty principle: a mathematical survey.  J. Fourier Anal. Appl., 3(3):207–238, 1997.
  * [34] Avi Wigderson and Yuval Wigderson.  The uncertainty principle: variations on a theme.  Bull. Amer. Math. Soc. (N.S.), 58(2):225–261, 2021.
  * [35] Hermann Weyl.  The Theory of Groups and Quantum Mechanics.  Dover Publications INC, 1950.
  * [36] David L. Donoho and Philip B. Stark.  Uncertainty principles and signal recovery.  SIAM J. Appl. Math., 49(3):906–931, 1989.
  * [37] Saifallah Ghobber and Philippe Jaming.  On uncertainty principles in the finite dimensional setting.  Linear Algebra Appl., 435(4):751–768, 2011.
  * [38] Terence Tao.  An uncertainty principle for cyclic groups of prime order.  Math. Res. Lett., 12(1):121–127, 2005.
  * [39] H. P. Robertson.  The uncertainty principle.  Phys. Rev., 34:163–164, Jul 1929.
  * [40] Patrick J. Coles, Mario Berta, Marco Tomamichel, and Stephanie Wehner.  Entropic uncertainty relations and their applications.  Rev. Mod. Phys., 89:015002, Feb 2017.
  * [41] H. L. Cycon, R. G. Froese, W. Kirsch, and B. Simon.  Schrödinger operators with application to quantum mechanics and global geometry.  Texts and Monographs in Physics. Springer-Verlag, Berlin, study edition, 1987.
  * [42] James S. Howland.  Perturbation theory of dense point spectra.  J. Funct. Anal., 74(1):52–80, 1987.
  * [43] Tosio Kato.  Positive commutators $i[f(P),g(Q)]$.  J. Funct. Anal., 96(1):117–129, 1991.
  * [44] Ira Herbst and Thomas L. Kriete.  The Howland-Kato commutator problem.  In Analysis and operator theory, volume 146 of Springer Optim. Appl., pages 191–223. Springer, Cham, 2019.
  * [45] David Deutsch.  Uncertainty in quantum measurements.  Phys. Rev. Lett., 50:631–633, Feb 1983.
  * [46] Hans Maassen and J. B. M. Uffink.  Generalized entropic uncertainty relations.  Phys. Rev. Lett., 60:1103–1106, Mar 1988.
  * [47] Kais Abdelkhalek, René Schwonnek, Hans Maassen, Fabian Furrer, Jörg Duhme, Philippe Raynal, Berthold-Georg Englert, and Reinhard F. Werner.  Optimality of entropic uncertainty relations.  International Journal of Quantum Information, 13(06):1550045, 2015\.
  * [48] Mark Hillery.  Total noise and nonclassical states.  Phys. Rev. A, 39:2994–3002, Mar 1989.
  * [49] Terence Tao.  Fuglede’s conjecture is false in 5 and higher dimensions.  Math. Res. Lett., 11(2-3):251–258, 2004.
  * [50] This last statement is false when $A$ and $B$ have degenerate spectra. To see this take $A=\mathbb{I}=B$ and choose two bases for which $M_{{\mathcal{A}},{\mathcal{B}}}<1$.
  * [51] Terence Tao.  Fuglede’s conjecture is false in 5 and higher dimensions.  Math. Res. Lett., 11(2-3):251–258, 2004.