**information-theory**937

[1802.07181] Algorithmic Information Dynamics of Persistent Patterns and Colliding Particles in the Game of Life

7 days ago by Vaguery

Without loss of generalisation to other systems, including possibly non-deterministic ones, we demonstrate the application of methods drawn from algorithmic information dynamics to the characterisation and classification of emergent and persistent patterns, motifs and colliding particles in Conway's Game of Life (GoL), a cellular automaton serving as a case study illustrating the way in which such ideas can be applied to a typical discrete dynamical system. We explore the issue of local observations of closed systems whose orbits may appear open because of inaccessibility to the global rules governing the overall system. We also investigate aspects of symmetry related to complexity in the distribution of patterns that occur with high frequency in GoL (which we thus call motifs) and analyse the distribution of these motifs with a view to tracking the changes in their algorithmic probability over time. We demonstrate how the tools introduced are an alternative to other computable measures that are unable to capture changes in emergent structures in evolving complex systems that are often too small or too subtle to be properly characterised by methods such as lossless compression and Shannon entropy.

cellular-automata
information-theory
not-the-way-I'd-go
to-understand
purdy-pitchers
compression
consider:individuation
consider:foreground-and-background
7 days ago by Vaguery

[1602.06093] Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches

6 weeks ago by Vaguery

This article introduces new tools to study self-organisation in a family of simple cellular automata which contain some particle-like objects with good collision properties (coalescence) in their time evolution. We draw an initial configuration at random according to some initial σ-ergodic measure μ, and use the limit measure to descrbe the asymptotic behaviour of the automata. We first take a qualitative approach, i.e. we obtain information on the limit measure(s). We prove that only particles moving in one particular direction can persist asymptotically. This provides some previously unknown information on the limit measures of various deterministic and probabilistic cellular automata: 3 and 4-cyclic cellular automata (introduced in [Fis90b]), one-sided captive cellular automata (introduced in [The04]), N. Fat{è}s' candidate to solve the density classification problem [Fat13], self stabilization process toward a discrete line [RR15]... In a second time we restrict our study to to a subclass, the gliders cellular automata. For this class we show quantitative results, consisting in the asymptotic law of some parameters: the entry times (generalising [KFD11]), the density of particles and the rate of convergence to the limit measure.

cellular-automata
self-organization
feature-extraction
feature-construction
define-your-terms
information-theory
nonlinear-dynamics
to-understand
6 weeks ago by Vaguery

[1704.08679] Age-Minimal Transmission in Energy Harvesting Two-hop Networks

6 weeks ago by Vaguery

We consider an energy harvesting two-hop network where a source is communicating to a destination through a relay. During a given communication session time, the source collects measurement updates from a physical phenomenon and sends them to the relay, which then forwards them to the destination. The objective is to send these updates to the destination as timely as possible; namely, such that the total age of information is minimized by the end of the communication session, subject to energy causality constraints at the source and the relay, and data causality constraints at the relay. Both the source and the relay use fixed, yet possibly different, transmission rates. Hence, each update packet incurs fixed non-zero transmission delays. We first solve the single-hop version of this problem, and then show that the two-hop problem is solved by treating the source and relay nodes as one combined node, with some parameter transformations, and solving a single-hop problem between that combined node and the destination.

queueing-theory
information-theory
multiobjective-optimization
rather-interesting
to-write-about
to-simulate
consider:looking-to-see
6 weeks ago by Vaguery

[1807.04271] A quantum-inspired classical algorithm for recommendation systems

10 weeks ago by Vaguery

A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an m×n matrix of small rank k. We give the first classical algorithm to produce a recommendation in O(poly(k)polylog(m,n)) time, which is an exponential improvement on previous algorithms that run in time linear in m and n. Our strategy is inspired by a quantum algorithm by Kerenidis and Prakash: like the quantum algorithm, instead of reconstructing a user's full list of preferences, we only seek a randomized sample from the user's preferences. Our main result is an algorithm that samples high-weight entries from a low-rank approximation of the input matrix in time independent of m and n, given natural sampling assumptions on that input matrix. As a consequence, we show that Kerenidis and Prakash's quantum machine learning (QML) algorithm, one of the strongest candidates for provably exponential speedups in QML, does not in fact give an exponential speedup over classical algorithms.

recommendations
algorithms
quantum-computing
classical-computing
rather-interesting
information-theory
to-understand
10 weeks ago by Vaguery

[1808.02679] Age of Information Upon Decisions

11 weeks ago by Vaguery

We consider an M/M/1 update-and-decide system where Poisson distributed decisions are made based on the received updates. We propose to characterize the freshness of the received updates at decision epochs with Age upon Decisions (AuD). Under the first-come-first-served policy (FCFS), the closed form average AuD is derived. We show that the average AuD of the system is determined by the arrival rate and the service rate, and is independent of the decision rate. Thus, merely increasing the decision rate does not improve the timeliness of decisions. Nevertheless, increasing the arrival rate and the service rate simultaneously can decrease the average AuD efficiently.

queueing-theory
information-theory
planning
simulation
rather-interesting
to-write-about
11 weeks ago by Vaguery

[1309.3441] On the shape of subword complexity sequences of finite words

12 weeks ago by Vaguery

The subword complexity of a word w over a finite alphabet is a function that assigns for each positive integer n, the number of distinct subwords of length n in w. The subword complexity of a word is a good measure of the randomness of the word and gives insight to what the word itself looks like. In this paper, we discuss the properties of subword complexity sequences, and consider different variables that influence their shape. We also compute the number of distinct subword complexity sequences for certain lengths of words over different alphabets, and state some conjectures about the growth of these numbers.

strings
combinatorics
enumeration
pattern-discovery
complexity-measures
information-theory
rather-interesting
to-write-about
for-puzzles
you-know-for-kids
12 weeks ago by Vaguery

[1611.03060] The Non-convex Geometry of Low-rank Matrix Optimization

december 2018 by Vaguery

This work considers two popular minimization problems: (i) the minimization of a general convex function f(X) with the domain being positive semi-definite matrices; (ii) the minimization of a general convex function f(X) regularized by the matrix nuclear norm ‖X‖∗ with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable X=UU⊤ (for semi-definite matrices) or X=UV⊤ (for general matrices) and also replace the nuclear norm ‖X‖∗ with (‖U‖2F+‖V‖2F)/2. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local search algorithms to find a global optimizer even with random initializations.

optimization
representation
matrices
to-understand
algorithms
mathematical-programming
information-theory
to-translate
december 2018 by Vaguery

**related tags**

Copy this bookmark: