Category Archives: Information Theory

Multiscale Structure of More-than-Binary Variables

When I face a writing task, my two big failure modes are either not starting at all and dragging my feet indefinitely, or writing far too much and having to cut it down to size later. In the latter case, my problem isn’t just that I go off on tangents. I try to answer every conceivable objection, including those that only I would think of. As a result, I end up fighting a rhetorical battle that only I know about, and the prose that emerges is not just overlong, but arcane and obscure. Furthermore, if the existing literature on a subject is confusing to me, I write a lot in the course of figuring it out, and so I end up with great big expository globs that I feel obligated to include with my reporting on what I myself actually did. That’s why my PhD thesis set the length record for my department by a factor of about three.

I have been experimenting with writing scientific pieces that are deliberately bite-sized to begin with. The first such experiment that I presented to the world, “Sporadic SICs and the Normed Division Algebras,” was exactly two pages long in its original form. The version that appeared in a peer-reviewed journal was slightly longer; I added a paragraph of context and a few references.

My latest attempt at a mini-paper (articlet?) is based on a blog post from a few months back. I polished it up, added some mathematical details, and worked in a comparison with other research that was published since I posted that blog item. The result is still fairly short:

More Google Scholar Irregularities

A few years ago, I noticed a glitch in a paper that colleagues of mine had published back in 2002. A less-than sign in an inequality should have been a less-than-or-equals. This might have been a transcription error during the typing-up of the work, or it could have entered during some other phase of the writing process. Happens to the best of us! Algebraically, it was equivalent to solving an equation
\[ ax^2 + bx + c = 0 \] with the quadratic formula,
\[ x = \frac{-b \pm \sqrt{b^2 – 4ac}}{2a},\] and neglecting the fact that if the expression under the square root sign equals zero, you still get a real solution.

This sort of glitch is usually not worth a lot of breath, though I do tend to write in when I notice them, to keep down the overall confusingness of the scientific literature. In this case, however, there’s a surprise bonus. The extra solutions you pick up turn out to have a very interesting structure to them, and they include mathematical objects that were already interesting for other reasons. So, I wrote a little note explaining this. In order to make it self-contained, I had to lay down a bit of background, and with one thing and another, the little note became more substantial. Too substantial, I learned: The journal that published the original paper wouldn’t take it as a Comment on that paper, because it said too many new things! Eventually, after a little more work, it found a home:

The number of citations that Google Scholar lists for this paper (one officially published in a journal, mind) fluctuates between 5 and 6. I think it wavers on whether to include a paper by Szymusiak and Słomczyński (Phys. Rev. A 94, 012122 = arXiv:1512.01735 [quant-ph]). Also, if you compare against the NASA ADS results, it turns out that Google Scholar is missing other citations, too, including a journal-published item by Bellomo et al. (Int. J. Quant. Info. 13, 2 (2015), 1550015 = arXiv:1504.02077 [quant-ph]).

As I said in 2014, this would be a rather petty thing to care about, if people didn’t rely on these metrics to make decisions! And, as it happens, all the problems I noted then are still true now.

Multiscale Structure, Information Theory, Explosions

I’d like to talk a bit about using information theory to quantify the intuition that a complex system exhibits structure at multiple scales of organization. My friend and colleague Ben Allen wrote an introduction to this a while ago:

Ben’s blog post is a capsule introduction to this article that he and I wrote with Yaneer Bar-Yam:

I also cover this topic, as well as a fair bit of background on how to relate probability and information, in my PhD thesis:

In this post, I’ll carry the ideas laid out in these sources a little bit farther in a particular direction.
Continue reading Multiscale Structure, Information Theory, Explosions

New Paper Dance

M. Appleby, C. A. Fuchs, B. C. Stacey and H. Zhu, “Introducing the Qplex: A Novel Arena for Quantum Theory,” arXiv:1612.03234 [quant-ph] (2016).

Abstract:

We reconstruct quantum theory starting from the premise that, as Asher Peres remarked, “Unperformed experiments have no results.” The tools of modern quantum information theory, and in particular the symmetric informationally complete (SIC) measurements, provide a concise expression of how exactly Peres’s dictum holds true. That expression is a constraint on how the probability distributions for outcomes of different, mutually exclusive experiments mesh together, a type of constraint not foreseen in classical thinking. Taking this as our foundational principle, we show how to reconstruct the formalism of quantum theory in finite-dimensional Hilbert spaces. Along the way, we derive a condition for the existence of a $d$-dimensional SIC.

Also available through SciRate, where I have a whole profile.

New Paper Dance

B. C. Stacey, “Geometric and Information-Theoretic Properties of the Hoggar Lines” (2016), arXiv:1609.03075 [quant-ph].

We take a tour of a set of equiangular lines in eight-dimensional Hilbert space. This structure defines an informationally complete measurement, that is, a way to represent all quantum states of three-qubit systems as probability distributions. Investigating the shape of this representation of state space yields a pattern of connections among a remarkable spread of mathematical constructions. In particular, studying the Shannon entropy of probabilistic representations of quantum states leads to an intriguing link between the questions of real and of complex equiangular lines. Furthermore, we will find relations between quantum information theory and mathematical topics like octonionic integers and the 28 bitangents to a quartic curve.

All things told, SIC-POVMs are just about the damnedest things I’ve ever studied in mathematics.

(Also listed on SciRate.)

Multiscale Structure via Information Theory

We have scienced:

B. Allen, B. C. Stacey and Y. Bar-Yam, “An Information-Theoretic Formalism for Multiscale Structure in Complex Systems” [arXiv:1409.4708].

We develop a general formalism for representing and understanding structure in complex systems. In our view, structure is the totality of relationships among a system’s components, and these relationships can be quantified using information theory. In the interest of flexibility we allow information to be quantified using any function, including Shannon entropy and Kolmogorov complexity, that satisfies certain fundamental axioms. Using these axioms, we formalize the notion of a dependency among components, and show how a system’s structure is revealed in the amount of information assigned to each dependency. We explore quantitative indices that summarize system structure, providing a new formal basis for the complexity profile and introducing a new index, the “marginal utility of information”. Using simple examples, we show how these indices capture intuitive ideas about structure in a quantitative way. Our formalism also sheds light on a longstanding mystery: that the mutual information of three or more variables can be negative. We discuss applications to complex networks, gene regulation, the kinetic theory of fluids and multiscale cybernetic thermodynamics.

There’s much more to do, but for the moment, let this indicate my mood:

#WhyTheQuantum

One day, I’ll be able to explain the story behind how I got into this, but looking back on all the oddities of it, I’m not sure that a medium other than manga could do it justice.

My Struggles with the Block Universe [arXiv:1405.2390]

Christopher A. Fuchs, Maximilian Schlosshauer (foreword), Blake C. Stacey (editor)

This document is the second installment of three in the Cerro Grande Fire Series. Like its predecessor arXiv:quant-ph/0105039, “Notes on a Paulian Idea,” it is a collection of letters written to various friends and colleagues, most of whom regularly circuit this archive. The unifying theme of all the letters is that each has something to do with the quantum. Particularly, the collection chronicles the emergence of Quantum Bayesianism as a robust view of quantum theory, eventually evolving into the still-more-radical “QBism” (with the B standing for no particular designation anymore), as it took its most distinctive turn away from various Copenhagen Interpretations. Included are many anecdotes from the history of quantum information theory: for instance, the story of the origin of the terms “qubit” and “quantum information” from their originator’s own mouth, a copy of a rejection letter written by E. T. Jaynes for one of Rolf Landauer’s original erasure-cost principle papers, and much more. Specialized indices are devoted to historical, technical, and philosophical matters. More roundly, the document is an attempt to provide an essential ingredient, unavailable anywhere else, for turning QBism into a live option within the vast spectrum of quantum foundational thought.

As the comment field says, “CAUTION, do not unthinkingly print from a printer: 2,348 pages, 4 indices, 6 figures, with extensive hyperlinking.”

MSwtBU was originally submitted to the arXiv on 10 May 2014, the anniversary of the predecessor volume and before that of the Cerro Grande Fire, which started the whole business. To my knowledge, it is the longest item currently on the arXiv.

omg 2000+ pages. There goes my free time.
— Dave Bacon, via Twitter

Currently Reading

Xiaotie Denga and Li-Sha Huang (2006), “On the complexity of market equilibria with maximum social welfare” Information Processing Letters 97, 1: 4–11 [DOI] [PDF].

We consider the computational complexity of the market equilibrium problem by exploring the structural properties of the Leontief exchange economy. We prove that, for economies guaranteed to have a market equilibrium, finding one with maximum social welfare or maximum individual welfare is NP-hard. In addition, we prove that counting the number of equilibrium prices is #P-hard.

Found by citation-hopping from here.

Currently Reading

Juan A. Bonachela, Haye Hinrichsen, Miguel A. Munoz, “Entropy estimates of small data sets” J. Phys. A: Math. Theor. 41 (2008). arXiv: 0804.4561.

Estimating entropies from limited data series is known to be a non-trivial task. Naive estimations are plagued with both systematic (bias) and statistical errors. Here, we present a new “balanced estimator” for entropy functionals (Shannon, Rényi and Tsallis) specially devised to provide a compromise between low bias and small statistical errors, for short data series. This new estimator out-performs other currently available ones when the data sets are small and the probabilities of the possible outputs of the random variable are not close to zero. Otherwise, other well-known estimators remain a better choice. The potential range of applicability of this estimator is quite broad specially for biological and digital data series.

As an exercise, discuss the relation of this approach to the coincidence-based methods of Ma, Bialas et al.

Categorical Information Theory

Ben Allen is now on the arXivotubes, with a category-theoretic arithmetic of information.

The concept of information has found application across the sciences. However, the conventional measures of information are not appropriate for all situations, and a more general mathematical concept is needed. In this work we give axioms that characterize the arithmetic of information, i.e. the way that pieces of information combine with each other. These axioms allow for a general notion of information functions, which quantify the information transmitted by a communication system. In our formalism, communication systems are represented as category-theoretic morphisms between information sources and destinations. Our framework encompasses discrete, continuous, and quantum information measures, as well as familiar mathematical functions that are not usually associated with information. We discuss these examples and prove basic results on the general behavior of information.

It looks like a discussion about this is starting over at the n-Category Café. If I didn’t have to spend today cutting down a 12-page paper to eight pages for an overpriced book of conference proceedings which nobody will read, I’d totally be writing more about it!

Aaronson on Turing, Gödel and Searle

Computer-science guru Scott Aaronson has begun to put lecture notes for his “Great Ideas In Theoretical Computer Science” course online. (That’s 6.080 in MIT-speak: words are for the weak.) Prepared by the students and edited by the instructors, the notes are terse but clear and enjoyable. I particularly like lecture 6, “Minds and Machines,” of which the following is a taste:

We already established that no Turing Machine exists can solve the halting problem. If we had a proof system that could analyze any Turing machine and prove if it halted or did not halt, we could use this system to solve the halting problem by brute force (also known as the “British Museum algorithm”) by trying every possible string that might be a proof. You would either terminate and find a proof that it halts or terminate and find a proof that it doesn’t halt. If this proof system was sound and complete, it would violate the unsolvability of the halting problem. Therefore, there is no such sound and complete proof system.

I also like this bit:
Continue reading Aaronson on Turing, Gödel and Searle

Shorter Uncommon Descent

BPSDBTyler DiPietro finds a fresh example of steaming creationist nonsense at the weblog of Dembski and sycophants, Uncommon Descent. I summarize for the busy reader:

Because running an image of a face through a software filter makes it look less like a face, Darwin was a fuddy-duddy and materialism is on its last leg.

The cream on the cocoa is, however, this bit, from a commenter:

I’m not sure about the CSI [complex specified information] decreasing, however. Anyone able to get values of the CSI for each picture?

Gee, given that “complex specified information” has never been consistently defined, I wonder how one could compute it.