Search

Let $T_0$ be the transition matrix of a purely clustered Markov chain, i.e. a direct sum of $k \geq 2$ irreducible stochastic matrices. Given a perturbation $T(x) = T_0 + xE$ of $T_0$ such that $T(x)$ is also stochastic, how small must $x$ be in order for us to recover the indices of the direct summands of $T_0$? We give a simple algorithm based on the orthogonal projection matrix onto the left or right singular subspace corresponding to the $k$ smallest singular values of $I - T(x)$ which allows for exact recovery all clusters when $x = O\left(\frac{\sigma_{n - k}}{||E||_2\sqrt{n_1}}\right)$ and approximate recovery of a single cluster when $x = O\left(\frac{\sigma_{n - k}}{||E||_2}\right)$, where $n_1$ is the size of the largest cluster and $\sigma_{n - k}$ the $(k + 1)$st smallest singular value of $T_0$.

Suppose that $T$ is a stochastic matrix. We propose an algorithm for identifying clusters in the Markov chain associated with $T$. The algorithm is recursive in nature, and in order to identify clusters, it uses the sign pattern of a left singular vector associated with the second smallest singular value of the Laplacian matrix $I-T.$ We prove a number of results that justify the algorithm's approach, and illustrate the algorithm's performance with several numerical examples., Comment: 41 pages, 10 figures

We analyze a quantum version of the Monge--Kantorovich optimal transport problem. The quantum transport cost related to a Hermitian cost matrix $C$ is minimized over the set of all bipartite coupling states $\rho^{AB}$ with fixed reduced density matrices $\rho^A$ and $\rho^B$ of size $m$ and $n$. The minimum quantum optimal transport cost $\rT^Q_{C}(\rho^A,\rho^B)$ can be efficiently computed using semidefinite programming. In the case $m=n$ the cost $\rT^Q_{C}$ gives a semidistance if and only if $C$ is positive semidefinite and vanishes exactly on the subspace of symmetric matrices. Furthermore, if $C$ satisfies the above conditions, then $\sqrt{\rT^Q_{C}}$ induces a quantum analogue of the Wasserstein-2 distance. Taking the quantum cost matrix $C^Q$ to be the projector on the antisymmetric subspace, we provide a semi-analytic expression for $\rT^Q_{C^Q}$ for any pair of single-qubit states and show that its square root yields a transport distance on the Bloch ball. Numerical simulations suggest that this property holds also in higher dimensions. Assuming that the cost matrix suffers decoherence and that the density matrices become diagonal, we study the quantum-to-classical transition of the Earth mover's distance, propose a continuous family of interpolating distances, and demonstrate that the quantum transport is cheaper than the classical one. Furthermore, we introduce a related quantity -- the SWAP-fidelity -- and compare its properties with the standard Uhlmann--Jozsa fidelity. We also discuss the quantum optimal transport for general $d$-partite systems., Comment: A detailed and expanded version of most mathematical results in arXiv:2102.07787: "Quantum Monge-Kantorovich problem and transport distance between density matrices". 61 pages

A quantum version of the Monge--Kantorovich optimal transport problem is analyzed. The transport cost is minimized over the set of all bipartite coupling states $\rho^{AB}$, such that both of its reduced density matrices $\rho^A$ and $\rho^B$ of dimension $N$ are fixed. We show that, selecting the quantum cost matrix to be proportional to the projector on the antisymmetric subspace, the minimal transport cost leads to a semidistance between $\rho^A$ and $\rho^B$, which is bounded from below by the rescaled Bures distance and from above by the root infidelity. In the single qubit case we provide a semi-analytic expression for the optimal transport cost between any two states and prove that its square root satisfies the triangle inequality and yields an analogue of the Wasserstein distance of order two on the set of density matrices. We introduce an associated measure of proximity of quantum states, called SWAP-fidelity, and discuss its properties and applications in quantum machine learning., Comment: 15 pages including appendices, 4 figures. Version v2 includes a new quantity, SWAP-fidelity, and some applications

This study focused on people in Edinburgh with low qualifications, meaning those with at most a lower secondary qualification who experience a high risk of poverty and social exclusion, and explored green job opportunities that exist for them, including those that would require reskilling (training to obtain different skills) or upskilling (training to obtain more advanced skills). In this study (unless stated otherwise), green jobs are understood as jobs in businesses that produce goods or provide services that benefit the environment or conserve natural resources, and green skills denote skills needed to adapt products, services and processes to climate change and the related environmental requirements and regulations. Evidence presented here includes national-level data (where regional and local information was not available) and focuses on data specific to green jobs or people with low qualifications. In Edinburgh, the largest potential for green jobs for people with low qualifications exists in construction (and includes occupations such as plasterers, dryliners, glazers, plumbers and heating technicians), in transport (as plant mechanics and fitters) and in manufacturing (as machine and plant operators, and metal and machinery workers). There are only a few interventions aimed at developing green skills for people with low qualifications. Most of these focused on young people. Full details can be found in the main report. [For the main report, "Green Jobs and Skills Development for Disadvantaged Groups. Research Report," see ED624858.]

We consider the exact recovery problem in the hypergraph stochastic block model (HSBM) with $k$ blocks of equal size. More precisely, we consider a random $d$-uniform hypergraph $H$ with $n$ vertices partitioned into $k$ clusters of size $s = n / k$. Hyperedges $e$ are added independently with probability $p$ if $e$ is contained within a single cluster and $q$ otherwise, where $0 \leq q < p \leq 1$. We present a spectral algorithm which recovers the clusters exactly with high probability, given mild conditions on $n, k, p, q$, and $d$. Our algorithm is based on the adjacency matrix of $H$, which is a symmetric $n \times n$ matrix whose $(u, v)$-th entry is the number of hyperedges containing both $u$ and $v$. To the best of our knowledge, our algorithm is the first to guarantee exact recovery when the number of clusters $k=\Theta(\sqrt{n})$.

In the planted partition problem, the $n$ vertices of a random graph are partitioned into $k$ "clusters," and edges between vertices in the same cluster and different clusters are included with constant probability $p$ and $q$, respectively (where $0 \le q < p \le 1$). We give an efficient spectral algorithm that recovers the clusters with high probability, provided that the sizes of any two clusters are either very close or separated by $\geq \Omega(\sqrt n)$. We also discuss a generalization of planted partition in which the algorithm's input is not a random graph, but a random real symmetric matrix with independent above-diagonal entries. Our algorithm is an adaptation of a previous algorithm for the uniform case, i.e., when all clusters are size $n / k \geq \Omega(\sqrt n)$. The original algorithm recovers the clusters one by one via iterated projection: it constructs the orthogonal projection operator onto the dominant $k$-dimensional eigenspace of the random graph's adjacency matrix, uses it to recover one of the clusters, then deletes it and recurses on the remaining vertices. We show herein that a similar algorithm works in the nonuniform case., Comment: 22 pages, 4 figures

In this paper, we consider the planted partition model, in which $n = ks$ vertices of a random graph are partitioned into $k$ "clusters," each of size $s$. Edges between vertices in the same cluster and different clusters are included with constant probability $p$ and $q$, respectively (where $0 \le q < p \le 1$). We give an efficient algorithm that, with high probability, recovers the clusters as long as the cluster sizes are are least $\Omega(\sqrt{n})$. Informally, our algorithm constructs the projection operator onto the dominant $k$-dimensional eigenspace of the graph's adjacency matrix and uses it to recover one cluster at a time. To our knowledge, our algorithm is the first purely spectral algorithm which runs in polynomial time and works even when $s = \Theta(\sqrt n)$, though there have been several non-spectral algorithms which accomplish this. Our algorithm is also among the simplest of these spectral algorithms, and its proof of correctness illustrates the usefulness of the Cauchy integral formula in this domain., Comment: 21 pages + title page