Sparsification: In Theory and Practice

Srilal Krishnan

Iona College, New Rochelle, USA.

DOI: 10.4236/jamp.2020.81008                

Abstract

The Kadison-Singer problem has variants in different branches of the sciences and one of these variants was proved in 2013. Based on the idea of “sparsification” and with its origins in quantum physics, at the sixtieth anniversary of the problem, we revisit the problem in its original formulation and also explore its transition to a result with wide ranging applications. We also describe how the notion of “sparsification” transcended various fields and how this notion led to resolution of the problem.

Keywords

Sparsification, C*-Algebra, Kadison-Singer Problem

1. Introduction and History

The word “sparsification” has great relevance in modern society. In data mining, data scientists constantly strive to construct synopsis of data such that relevant features of the data are retained. In another sense, the endeavor is to “sparsify” data without losing its most important characteristics. In networking and graph theory, mathematicians and computer scientists strive to “sparsify” complex networks while trying to retain essential properties of the original network. In other words, the endeavor is to remove suitable vertices and edges to construct a subgraph which can “decently” approximate the original network. The words synopsis and approximation used in each of the above categories are synonyms but to be more mathematically relevant it is important to mention that the idea of approximation is based on comparing the spectrum of the graph/network and see if they are the same. It is clear that, this idea of “sparsification” will have implications in multitude of applied problems including networks involving the Traveling salesman problem. It might be interesting to note that the idea of “sparsification” was of great interest decades back and one of the greatest mathematical conjectures “The Kadison-Singer Problem” was an outcome of this idea. This problem was resolved by Marcus, Spielman and Srivastava in 2013 [1]. The resolution provided scientists with tools necessary to implement the idea of “sparsification” in various applied fields. We talk a bit about the history of this problem and how the problem by itself had different formulations in applied fields of mathematics. Finally, we study and understand the problem in its most original formulation. We also discuss completion of the proof from the original paper after resolution of the conjecture. The history and the mathematics of this problem including its transition from a problem from physics to one in the engineering sciences and computer science is very interesting and has implications for other longstanding problems in these fields like the asymmetrical traveling salesman problem [2]. Next, we talk a bit about the history of the problem. The problem was posed by Kadison and Singer in 1959 in [3] and was motivated by Dirac’s work in quantum mechanics and the intent was to provide a mathematical framework for characterizing quantum systems and study if states of compatible observables have unique extensions to all observables in the quantum system. The problem is a query: Does every pure state on the diagonal subalgebra of the C^*-algebra of all bounded linear operators on ${\mathcal{l}}_2\left(\mathbb{N}\right)$ i.e. $B\left({\mathcal{l}}_2\left(\mathbb{N}\right)\right)$ extend uniquely to a pure state on all of $B\left({\mathcal{l}}_2\left(\mathbb{N}\right)\right)$ ? Kadison and Singer were of the opinion that the conjecture was possibly negative. In other words, their belief was that there are pure states $f\mathrm{,}g$ on $B\left({\mathcal{l}}_2\left(\mathbb{N}\right)\right)$ such that $f\ne g$ but $f=g$ on the diagonal subalgebra D of $B\left({\mathcal{l}}_2\left(\mathbb{N}\right)\right)$. In 1970’s, Joel Anderson sparked interest in this problem through his equivalent formulation in Frame theory. Frame theory has applications in engineering, particularly in signal processing and so this equivalent formulation generated lot of interest. In the year 2004, Nick Weaver reformulated the problem as a discrepancy problem involving vectors in $C^n$. These equivalent formulations with relevant proofs can be found in [4] and [5]. Using Nick Weaver’s combinatorial formulation of the Kadison-Singer problem, Marcus, Spielman and Srivastava eventually proved the theorem in 2013. Interestingly, their research in graph theory and computer science led them to the Kadison-Singer problem and it was not the other way around. It is also worth mentioning that their original study involved researching conditions to “sparsify” networks with appropriate edge and vertex removals without changing fundamental properties of the original network. The most surprising aspect of their resolution was that, contrary to the belief of Kadison and Singer and many other researchers, the conjecture was proved to be true. Recently, methods of this proof have been implemented in algorithmic complexities involving the Traveling Salesman problem and also in computational complexity theory [2] [6]. The Kadison-Singer problem whose journey originated from Quantum Mechanics and whose resolution has implications involving computational complexities of the Traveling Salesman problem has been fascinating. In this spirit, it might be worthy to revisit and understand the problem in its original formulation.

2. Understanding the Kadison-Singer Problem

The Kadison-Singer Problem was one of the major long standing unresolved problems in functional analysis. In order to understand this original problem of “sparsification”, we discuss some preliminaries. We will begin by defining a Hilbert space.

Definition 1. A Hilbert space H is a vector space having an inner product such that every Cauchy sequence in H has a limit in H.

Definition 2. A separable Hilbert space is a Hilbert space H that has a countable dense subset.

A relevant example of a separable Hilbert-space is ${\mathcal{l}}_2={\mathcal{l}}_2\left(\mathbb{N}\right)$.

Example 1. ${\mathcal{l}}_2={\mathcal{l}}_2\left(\mathbb{N}\right)$ is a separable Hilbert space with the orthonormal basis ${\left\{e_i\right\}}_{i\in \left(\mathbb{N}\right)}$, where ${\mathcal{l}}_2\left(\mathbb{N}\right)=\left\{\left(z_1,z_2,\cdots \right):z_i\in C;{\displaystyle \underset{i=1}{\overset{\infty }{\sum }}}{\left|z_i\right|}^2<\infty \right\}$. Note that $\mathbb{N}$ forms the indexing set. For $z=\left(z_1\mathrm{,}{z}_2\mathrm{,}\cdots \right)$ and $z^{\prime }=\left({z^{\prime }}_1\mathrm{,}{z^{\prime }}_2\mathrm{,}\cdots \right)$ in ${\mathcal{l}}_2\left(\mathbb{N}\right)$ ; the inner product is defined as follows: $\langle z,z^{\prime }\rangle ={\displaystyle \underset{i=1}{\overset{\infty }{\sum }}}{z}_i{{\bar{z}}^{\prime }}_i$.

The elements of ${\mathcal{l}}_2={\mathcal{l}}_2\left(\mathbb{N}\right)$ can be expressed as functions from the set of natural numbers N to the set of complex numbers C. We consider the set of all bounded linear operators on ${\mathcal{l}}_2\left(\mathbb{N}\right)$ i.e. $T\mathrm{<mo>\; :\; </mo>}{\mathcal{l}}_2\left(\mathbb{N}\right)\to {\mathcal{l}}_2\left(\mathbb{N}\right)$ and denote it by $B\left({\mathcal{l}}_2\left(\mathbb{N}\right)\right)$. Next, we define a C^*-algebra. One may refer to [7] for a detailed introduction to C^*-algebras and to [4], [8] and [9] for relevant examples.

Definition 3. A C^*-algebra A is a norm closed self-adjoint subalgebra of the operator algebra $B\left(H\right)$, for some Hilbert space H.

In other words, A is:

1) Closed in the norm topology of operators.

2) Closed under the operation of taking adjoints of operators.

Looking at the problem that originated in quantum mechanics, the observables of a quantum mechanical system are represented by $B\left(H\right)$.

Next, we will try to understand the notion of pure states on a C^*-algebra. We will start by describing a linear functional.

Definition 4. A linear functional on a C^*-algebra A is a linear map, say f from A to C.

The space consisting of linear functionals on a C^*-algebra A is called the dual space of A and is denoted by A’. We look at an example of linear functional on ${\mathcal{l}}_2\left(\mathbb{N}\right)$.

Example 2. Fix $z=\left(z_1,z_2,\cdots \right)\in {\mathcal{l}}_2\left(N\right)$ and consider $f\left(a\right)={\displaystyle \underset{i=1}{\overset{\infty }{\sum }}}{z}_i{a}_i$, where $a=\left(a_1,a_2,\cdots \right)\in {\mathcal{l}}_2\left(\mathbb{N}\right)$.

An example of a bounded linear operator on the infinite dimensional separable Hilbert space ${\mathcal{l}}_2={\mathcal{l}}_2\left(\mathbb{N}\right)$ will be an infinite dimensional matrix with complex entries but for the sake of simplicity, let us look at the two dimensional version of ${\mathcal{l}}_2={\mathcal{l}}_2\left(\mathbb{N}\right)$ and let us call it $l_{2_2}$. The algebra of bounded operators on

$l_{2_2}$ is $B\left(l_{2_2}\right)=\left\{A:A=\left[\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right];a_{ij}\in C,1\le i,j\le 2\right\}$. A linear functional on $B\left(l_{2_2}\right)$ is then in the form ${\displaystyle \underset{i=1}{\overset{2}{\sum }}}{\alpha }_{ij}{a}_{ij}$, ${\alpha }_{ij}\in C$, i.e. ${\alpha }_{11}{a}_{11}+{\alpha }_{12}{a}_{12}+{\alpha }_{21}{a}_{21}+{\alpha }_{22}{a}_{22}$. If we define the matrix $K=\left[\begin{array}{cc}{\alpha }_{11}& {\alpha }_{12}\\ {\alpha }_{21}& {\alpha }_{22}\end{array}\right]$, then this linear functional can be expressed in the form of trace of AK i.e. $tr\left(AK\right)$.

Also as mentioned previously, the observables of a quantum mechanical system are represented by $B\left(H\right)$ and a state of this system is a linear functional on $B\left(H\right)$.

Definition 5. A positive linear functional on a C^*-algebra is a linear functional f such that $f\left(x\right)\ge 0$ whenever $x\ge 0$. A state is defined to be a positive linear functional of norm 1.

Definition 6. A pure state is a state which is an extreme point of the set of all states of the C^*-algebra.

Here is an example of a pure state.

Example 3. For a unit element vector $z\in l_2\left(\mathbb{N}\right)$, a pure state on $B\left(l_2\left(\mathbb{N}\right)\right)$ is in the form $f_z\left(T\right)=\langle Tz\mathrm{,}z\rangle$.

Continuing with the example from above, if A is the identity matrix I, then $tr\left(IK\right)=1$ provided $tr\left(K\right)=1$. So a state on $B\left(l_{2_2}\right)$ should satisfy

$tr\left(K\right)=1$. In addition, for a state on $B\left(l_{2_2}\right)$, the additional condition on the state is that the matrix K is self-adjoint i.e. the conjugate transpose of the matrix K is itself and all its principal minors are non-negative. For example, this happens in a situation where the matrix K has non-negative real entries. Consider

the subalgebra $S=\left\{A:A=\left[\begin{array}{cc}{a}_{11}& 0\\ 0& a_{22}\end{array}\right];a_{ij}\in C,1\le i,j\le 2\right\}$ of $B\left(l_{2_2}\right)$ and consider the pure state on S given by $a_{11}$. We need to find states on $B\left(l_{2_2}\right)$ that is an extension of this pure state on S. These states will be in the form $tr\left(AK\right)$ with $K=\left[\begin{array}{cc}1& a_{12}\\ a_{21}& 0\end{array}\right]$ ; and satisfying ${\bar{a}}_{12}=a_{21}$. For the condition that all principal minors be non-negative, this happens if $a_{12}{a}_{21}\ge 0$ i.e. $a_{12}{\bar{a}}_{12}\ge 0$. If $a_{12}=x+iy$, $a_{12}{\bar{a}}_{12}\ge 0$ implies $\left(x+iy\right)\left(x-iy\right)\ge 0$ i.e. $x^2+y^2\ge 0$. So $x=y=0$. In other words $K=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right]$ ; and $tr\left(AK\right)=a_{11}$. Thus the state on S given by $a_{11}$ has unique extension to all of $B\left(l_{2_2}\right)$. As seen for this example, the Kadison-Singer problem as resolved is true.

Next, we state the Krein-Milman theorem, see [10]. A general statement of the theorem is given below:

Theorem 1. If C is a compact convex subset of a locally convex topological vector space A, then C is the closed convex hull of its extreme points.

Recall that, a pure state is a state which is an extreme point of the set of all states of the C^*-algebra. The existence of pure states is guaranteed by the following observations:

1) The set of states of the C^*-algebra A is a convex subset of the dual space of A(A’). It is also compact in the weak*-topology on A’, where the weak*-topology is defined by the semi-norms $\left|f\left(x\right)\right|$ on the dual space A’.

2) By Krein-Milman theorem, the set of states is the closed convex hull of its extreme points.

These extreme points are the pure states.

3. Extension of States

Hahn-Banach theorem is one of the profound theorems in functional analysis which has far reaching applications in the sciences, for example thermodynamics [11].

Theorem 2. If C is a subspace of the normed linear space A and if f is a bounded linear functional on C then f can be extended to a bounded linear functional F on A such that $F|C=f$, and $\Vert F\Vert =\Vert f\Vert$.

Thus, by Hahn-Banach theorem, a state on a C^*-subalgebra C of A is extended to A. The above observation in conjunction with the Krein-Milman theorem suggests that a pure state on the diagonal subalgebra of $B\left(l_2\left(\mathbb{N}\right)\right)$ extends to at least one pure state of $B\left(l_2\left(\mathbb{N}\right)\right)$. Is this extension unique? Recall that this was the Kadison-Singer conjecture.

4. Identification of the Diagonal Subalgebra of $B\left(l_2\left(\mathbb{N}\right)\right)$ (via Stone-Cech Compactification of $\mathbb{N}$ : $\beta (\mathbb{N}))$

The diagonal subalgebra of $B\left(l_2\left(\mathbb{N}\right)\right)$ with respect to the natural basis is $l_{\infty }\left(\mathbb{N}\right)$, where $l_{\infty }\left(\mathbb{N}\right)$ is defined as follows:

Definition 7. $l_{\infty }\left(\mathbb{N}\right)$ is the space of all bounded sequences with respect to the supnorm i.e. ${\Vert x\Vert }_{\infty }=\sup {\left|x_n\right|}_{n\in \mathbb{N}}$

We observe below that $l_{\infty }\left(\mathbb{N}\right)$ can be characterized using $\beta \left(\mathbb{N}\right)$ via the Stone-Cech compactification [12]. The Stone-Cech compactification of a space X that is not compact is a technique for constructing a compact Hausdorff space $\beta \left(X\right)$ which in layman’s terms is very similar to X. In technical terms, we construct a homeomorphism k from X to a subspace of $\beta \left(X\right)$ such that $k\left(X\right)$ is dense in $\beta \left(X\right)$. The set of natural numbers $\mathbb{N}$ is not compact. Implementing the above procedure for $\mathbb{N}$, every bounded function from $\mathbb{N}$ i.e. elements of $l_{\infty }\left(\mathbb{N}\right)$ extends to continuous functions on $\beta \left(\mathbb{N}\right)$.

Let $C\left(\beta \left(\mathbb{N}\right)\right)$ represent the space of continuous functions on $\beta \left(\mathbb{N}\right)$.

1) As seen before, we are able to identify $l_{\infty }\left(\mathbb{N}\right)$ with $C\left(\beta \left(\mathbb{N}\right)\right)$.

2) Pure states on $l_{\infty }\left(\mathbb{N}\right)$ correspond to homeomorphisms induced by evaluations at points in $\beta \left(\mathbb{N}\right)$.

Kadison and Singer have already proved in [3] that the pure states corresponding to points in $\mathbb{N}$ with the canonical basis vectors have unique pure state extensions. So the focus is on the pure states in $\beta \left(\mathbb{N}\right)-\mathbb{N}$. In other words, do pure states corresponding to $\beta \left(\mathbb{N}\right)-\mathbb{N}$ have unique extensions to pure states on all of $B\left(l_2\left(\mathbb{N}\right)\right)$ ? This was proved to be true in the equivalent formulation by Marcus, Spielman and Srivastava. These outstanding researchers were awarded the Polya prize in 2014 for their work.

5. Equivalent Formulations of the Kadison Singer Problem

Although the purpose of this paper is to provide a gentle introduction to the notion of sparsification with Kadison-Singer problem as foundational, it is important to state equivalent formulations of the problem for the benefit of the reader. This problem has equivalent formulations in Frame theory. In linear algebra, a frame of an inner product space is a generalization of a basis of a vector space to sets that may be linearly dependent [13]. Also, a sequence of vectors $\left(x_n\right)$ in a Hilbert space H is called a Reisz sequence if there exists constants $0<c\le C<\infty$

such that $c\left({\displaystyle \underset{n}{\sum }}{\left|a_n\right|}^2\right)\le {\Vert {\displaystyle \underset{n}{\sum }}{a}_n{x}_n\Vert }^2\le C\left({\displaystyle \underset{n}{\sum }}{\left|a_n\right|}^2\right)$ for all sequences $\left(a_n\right)\in l_2\left(N\right)$.

The equivalent formulations with relevant proofs can be found in [4] but is outlined below for the reader’s benefit.

1) Paving Conjecture: For $\epsilon >0$, there is a natural number r so that for every natural number n and for every linear operator T on $l_2^n$ whose matrix has zero diagonal, we can find a partition (i.e. a paving) ${\left\{A_j\right\}}_{j=1}^r$ of $\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$, so that $\Vert Q_{A_j}T{Q}_{A_j}\Vert \le \epsilon \Vert T\Vert$ for all $j=1,2,\cdots ,r$.

2) Bourgain-Tzafriri Conjecture: There is a universal constant $A>0$ so that for every $B>1$ there is a natural number $r=r\left(B\right)$ satisfying: For every natural number n if $T\mathrm{<mo>\; :\; </mo>}{l}_2^n\to l_2^n$ is a linear operator with $\Vert T\Vert \le B$ and $\Vert T{e}_i\Vert =1$

for all $i=1,2,\cdots ,n$, then there is a partition ${\left\{A_j\right\}}_{j=1}^r$ of $\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ so that for

all $j=1,2,\cdots ,r$. And for all choices of scalars all ${\left\{a_i\right\}}_{i\in A_j}$ we have

${\Vert {\displaystyle \underset{i\in A_j}{\sum }}{a}_{i}T{e}_i\Vert }^2\le A{\displaystyle \underset{i\in A_j}{\sum }}{\left|a_i\right|}^2$.

3) Feichtinger conjecture: Every bounded frame can be written as a finite union of Riesz basic sequences.

More recently, the resolution of Kadison-Singer Problem has generated lot of interest in computational complexity. Please refer to [2] and [6] for more information.

6. Conclusion

The notion of sparsification has been of great relevance in history and in modern society. The Kadison-Singer problem based on this notion is one of those unique problems that transcends various scientific disciplines, bridges the gap between pure and applied, instills in us the beauty of the nature of mathematics and its wholesomeness.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Marcus, A., Spielman, D.A. and Srivastava, N. (2015) Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem. Annals of Mathematics, 182, 327-350. https://doi.org/10.4007/annals.2015.182.1.8
[2]	Anari, N. and Gharan, S.O. (2015) The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP.
[3]	Kadison, R. and Singer, I. (1959) Extensions of Pure States. American Journal of Mathematics, 81, 383-400. https://doi.org/10.2307/2372748
[4]	Casazza, P.G. and Tremain, J.C. (2006) The Kadison-Singer Problem in Mathematics and Engineering. Proceedings of National Academy of Sciences of the USA, 103, 2032-2039. https://doi.org/10.1073/pnas.0507888103
[5]	Weaver, N. (2004) The Kadison-Singer Problem in Discrepancy Theory. Discrete Mathematics, 278, 227-239. https://doi.org/10.1016/S0012-365X(03)00253-X
[6]	Wigderson, A. (2017) Interactions of Computational Complexity Theory and Mathematics.
[7]	Davidson, K.R. (1996) C*-Algebras by Example. Vol. 6, Fields Institute Monographs, American Mathematical Society, Providence. https://doi.org/10.1090/fim/006
[8]	Casazza, P.G. and Weber, E. (2008) The Kadison-Singer Theorem and the Uncertainity Principle. Proceedings of the American Mathematical Society, 136, 4235-4243. https://doi.org/10.1090/S0002-9939-08-09564-6
[9]	Akemann, C.A., Tanbay, B. and Ulger, A. (2010) A Note on the Kadison-Singer Problem. Journal of Operator Theory, 62, 363-374.
[10]	Krein, M. and Milman, D. (1940) On Extreme Points of Regular Convex Sets. Studia Mathematica, 9, 133-138. https://doi.org/10.4064/sm-9-1-133-138
[11]	Feinberg, M. and Lavine, R. (1983) Thermodynamics Based on the Hahn-Banach Theorem: The Clausius Inequality. Archive for Rational Mechanics and Analysis, 82, 203-293. https://doi.org/10.1007/BF00261935
[12]	Akemann, C. and Paulsen, V. State-Extensions and the Kadison-Singer Problem. AIM Preprint. https://aimath.org/WWN/kadisonsinger/ARCC-ap.pdf
[13]	Kovačević, J. and Chebira, A. (2008) An Introduction to Frames. Foundations and Trends in Signal Processing, 2, 1-94. https://doi.org/10.1561/2000000006