Compressive algorithmic randomness: Gibbs-randomness proposition for massively energy efficient deep learning

Figure: Dual Tomographic Compression
Performance, Süzen, 2025.

Preamble

Randomness is elusive and its probably one of the outstanding concepts for human scientific endeavour, along with gravity. Kolmogorov complexity, appears to be so novel in trying to answering "what is randomness?". The idea that the length of the smallest model that can generate the random sequence determines its complexity was a turning point in history of science. Similarly, it implies choosing the simplest model for explaining a phenomenon. That's why Kolmogorov's work was also supported by the ideas of Solomonoff and Chaitin. A recent work, explores this algorithmic information from compression perspective with Gibbs entropy.

A strange tale of path from applied research to fundamental proposition. 

During study of model compression algorithm development, I have noticed an amazing behaviour that information, entropy and compression over compression process have a more in depth. 

New concepts in compression and randomness via train-compress cycles

Here, we explain the new concepts for both deep learning model compression and on the interplay between compression and algorithmic randomness.

Inverse compressed sensing (iCS): Normally CS procedure is applied to reconstruct an unknown signal with fewer measurements. In the case of deep learning train-compress, weights are known at one point in the training cycle. If we create hypothetical measurements, using CS formulations, we can reconstruct weights sparse projection. 

Dual Tomographic Compression: Applying iCS for the input and output of neuronal level, layer-wise, simultaneously.  

Weight rays:  An output reconstructed vector out of DTC; weights given sparsity level, though they are not generated in isolation but within train-compress cycle.

Gibbs randomness proposition : An extension of Kolmogorov complexity for a compression process. That, directed randomness is the same as complexity reduction, i.e., compression. 

Conclusion 

A new technique called DTC can be used to train deep learning with model compression on the fly. This gives rise to massively energy efficient deep learning, reaching almost ~98% reduction in energy use.  Moreover, the technique also demonstrated an extended version of Kolmogorov complexity. 

Further reading 

Paper & codes are released :

• Paper: Gibbs randomness-compression proposition: An efficient deep learning 
  arXiv:2505.23869 (2025)
• Codes: https://github.com/msuzen/research/tree/main/gibbs-randomness-compression 

Cite as 

 @misc{suzen25car, 

     title = {Compressive algorithmic randomness: <br>Gibbs-randomness proposition for massively energy efficient deep learning}, 

     howpublished = {\url{ https://science-memo.blogspot.com/2025/06/compressive-algorithmic-randomness.html}}, 

     author = {Mehmet Süzen},

     year = {2025}

}  

Matrix Cumulative Coherence: Fourier Bases, Random and Sensing Matrices

Compressive sampling (CS) is revolutionizing the way we process analog to digital conversion, our understanding of linear systems and the limits of information theory. One of the key concept in CS is that a signal can be represented in a sparse bases or it is already sparse. The novelty of sparsity bases is that when signal is randomly sampled, in a nutshell it can be recovered (or a solution can be found to a linear problem) with fewer samples. A land mark example is being sparse MRI.

The concept of choosing "more" sparse bases or CS sensing matrix lies in the measure of mutual coherence. It is defined as follows for a given matrix at order k.
$$  M(A, k) = max_{p} max_{p \ne q, q \in \Omega } \sum_{q} | <a_{p}, a_{q}> | / ( |a_{p}| |a_{q}|)$$ When k=1, it is easy to understand what it means. Basically we find the largest inner product among columns of the given matrix. Lower the value better the sparsity i.e. incoherence. However a single number may not be so informative, after all how low is better.  With the definition of David Donoho and Joel Tropp,  if M is slowly increasing then matrix said to be enchances sparsity. Larger value of k forms a set of columns $\Omega$, and the second colums are selected from this set i.e. second max argument in the above definition.

In a recent post I have shortly reviewed my R package for CS called R1magic. Its recent version 0.2 contains a functionality to compute $M(A, k)$.  Also now there is a public Github repository of the package. mutualCoherence function is written fully functional way. All operations for computing $M(A,k)$ performed in vectorial fashion in R, using function closures and apply. However, for much larger matrices, a low level implementation may be required.

Example

Here we shortly investigate coherence of Fourier, random and mixed bases in R.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

require("R1magic") set.seed(42) A <- DFTMatrix0(10) # Fourier Bases B <- matrix(rnorm(100), 10, 10) # Gaussian Random Matrix C <- A %*% B # A sensing matrix with A and B as above aa<-mutualCoherence(A, 8) bb<-mutualCoherence(A, 8) bb<-mutualCoherence(A, 8) aa [1] 1 1 1 1 1 1 1 1 bb [1] 0.6784574 1.2011489 1.7001046 2.1713561 2.4664608 2.7302690 2.7908302 [8] 2.9623327 cc [1] 0.7506222 1.3448452 1.8047043 2.1105348 2.3350516 2.4703822 2.5898766 [8] 2.6882250

We observe that mixed bases, where we define so called a CS matrix, matrix $C$ in above notation, with Fourier ($A$) and Random basis ($B$). Its mutual coherence increases slower than the pure random matrix with unit measure. This may signify a better incoherent basis.  However, since this is a "syntetic data', it does not tell any universal behaviour at all. A real data or signal measurement matrix  shall be tested for a better judgement of which bases is better to use in sparse recovery.  A recent paper in optical tomography uses this concept to identify a better sensing matrix in tomographic image reconstruction.