[2025-03-11]

$logo$

Code / Contact me @ laurent.perrinet@univ-amu.fr QR code

Sparse representations?

Paysage catalan (Le Chasseur)

to rephrase the expression “The Unreasonable Effectiveness of Mathematics” by Wigner, the “Unreasonable efficiency of vision” is playfully illustrated in this painting from Joan Miró, which allows us to depict this Catalan landscape with the a few strokes where our imagination will fill the gaps and signify the landscape, allowing us to imagine the hunter, the sardine or the plane.

the whole is the sum of a few parts

Sparse coding is a technique used in signal processing and machine learning to represent data in a more concise and efficient manner. It aims to find a sparse representation of the data, which means representing the data with only a small number of non-zero coefficients or activations. In sparse coding, a set of basis functions or atoms is typically defined, and the goal is to find a linear combination of these atoms that best represents the input data. The coefficients of this linear combination are often constrained to be sparse, meaning that only a few of them are allowed to be non-zero.

Sparse representations in computer vision

[[LP *et al*, 2004](https://laurentperrinet.github.io/publication/perrinet-04-tauc/)] — [LP *et al*, 2004]

Sparse representations in computer vision

Code @ A hitchhiker guide to Matching Pursuit

Sparse representations in computer vision

[[LP and Bednar, 2015]](https://laurentperrinet.github.io/publication/perrinet-bednar-15/) — [LP and Bednar, 2015]

Sparse representations in computer vision

[[LP, 2021](https://laurentperrinet.github.io/sciblog/posts/2021-03-27-density-of-stars-on-the-surface-of-the-sky.html)] — [LP, 2021]

Sparse representations in neuromorphic engineering

Ultimately, we get a list of events for each pixel that can be merged to represent the entire image. This list of events includes pixel addresses, times of occurrence, and polarities. Note that since events are generated over time, they are naturally sorted by their time of occurrence. These events are then transmitted in real time to the output bus, often via a USB3 connection. It’s interesting to draw a parallel between this process and the optic nerve that connects our retina to the brain. In fact, the output of the retina consists of a million ganglion cells that emit action potentials, which are the only source of information transmitted by the optic nerve.

https://www.researchgate.net/profile/Guido-Croon/publication/313221316/figure/fig2/AS:668997448134663@1536512829861/Picture-of-the-event-based-camera-employed-in-this-work-the-DVS_W640.jpg

Sparse representations in neuroscience

[[Brunel, 2001](https://books.google.fr/books?hl=fr&lr=&id=b8woDqWdTssC&oi=fnd&pg=PA307&ots=KNHQrJ-TsZ&sig=0WI2cq2RnMXC7fVTyjOEWZEdlCg&redir_esc=y#v=onepage&q&f=false)] — [Brunel, 2001]

Sparse representations in neuroscience

[[Mainen & Sejnowski, 1995](https://github.com/SpikeAI/2022_polychronies-review/blob/main/src/Figure_2_MainenSejnowski1995.ipynb)] — [Mainen & Sejnowski, 1995]

Sparse representations in neuroscience

[[Kremkow *et al*, 2016](https://laurentperrinet.github.io/publication/kremkow-16/)] — [Kremkow *et al*, 2016]

Sparse representations in neuroscience

Sparse representations?

Sparse representations in a nutshell

Sparse representations in a nutshell

[[Olshausen and Field (1997)](http://mplab.ucsd.edu/~marni/Igert/Olshaussen_1997.pdf)] — [Olshausen and Field (1997)]

Sparse representations in a nutshell

Generative model of image synthesis:

$I[x, y] = $ $\sum_{i=1}^{K} a[i] \cdot \phi[i, x, y]$ $ + \varepsilon[x, y]$

Where $\phi$ is a dictionary of $K$ atoms, $a$ is a sparse vector of coefficients, and $\varepsilon$ is a noise term.

[LP (2015)]

Sparse representations in a nutshell

Given an observation $I$,

$$ \begin{aligned} \mathcal{L}(a) & = - \log Pr( a | I ) \\ \end{aligned} $$

Sparse representations in a nutshell

Given an observation $I$,

$$ \begin{aligned} \mathcal{L}(a) & = - \log Pr( a | I ) \\ & = - \log Pr( I | a ) - \log Pr(a) \\ \end{aligned} $$

Sparse representations in a nutshell

Given an observation $I$,

$$ \begin{aligned} \mathcal{L}(a) & = - \log Pr( a | I ) \\ & = - \log Pr( I | a ) - \log Pr(a) \\ & = \frac{1}{2\sigma_n^2} \sum_{x, y} ( I[x, y] - \sum_{i=1}^{K} a[i] \cdot \phi[i, x, y])^2 - \sum_{i=1}^{K} \log Pr( a[i] ) \end{aligned} $$

Sparse representations in a nutshell

The problem is formalized as an optimization problem $a^\ast = \arg \min_a \mathcal{L}(a)$ with:

$$ \mathcal{L} = \frac{1}{2} \sum_{x, y} ( I[x, y] - \sum_{i=1}^{K} a[i] \cdot \phi[i, x, y])^2 + \lambda \cdot \sum_i ( a[i] \neq 0) $$

[LP (2015)]

Sparse representations in a nutshell

The problem is formalized as an optimization problem $a^\ast = \arg \min_a \mathcal{L}(a)$ with:

$$ \mathcal{L}(a) = \frac{1}{2} \sum_{x, y} ( I[x, y] - \sum_{i=1}^{K} a[i] \cdot \phi[i, x, y])^2 + \lambda \cdot \sum_{i=1}^{K} | a[i] | $$

Sparse representations in a nutshell

[[Rentzeperis *et al* (2023)](https://laurentperrinet.github.io/publication/rentzeperis-23/)] — [Rentzeperis *et al* (2023)]

Sparse representations in a nutshell

Neural implementation = gradient descent

LASSO = least absolute shrinkage and selection operator

Orthogonal Matching Pursuit (OMP): OMP is an iterative algorithm used for sparse signal recovery. It starts with an initial sparse solution and iteratively selects the most correlated dictionary atoms with the residual signal. OMP aims to minimize the L2 norm of the residual while maintaining sparsity. It has a greedy nature and can provide a near-optimal sparse solution.

Basis Pursuit (BP): Basis Pursuit is an optimization problem that seeks the sparsest solution to an underdetermined linear system of equations. It involves minimizing the L1 norm of the coefficient vector subject to a linear constraint. BP can be solved using linear programming techniques or convex optimization algorithms.

Iterative Soft Thresholding Algorithm (ISTA): ISTA is an iterative optimization algorithm commonly used in sparse coding. It alternates between a gradient descent step and a soft thresholding step. The gradient descent step minimizes the data fidelity term, and the soft thresholding step enforces sparsity by setting small coefficients to zero. ISTA converges to a sparse solution and can be used for dictionary learning.

FISTA (Fast Iterative Shrinkage-Thresholding Algorithm): FISTA is an accelerated version of ISTA that improves convergence speed. It incorporates momentum into the optimization process and achieves faster convergence rates.

ADMM (Alternating Direction Method of Multipliers): ADMM is an optimization technique that decomposes the original problem into smaller subproblems and solves them iteratively. It is often used for convex optimization problems with L1 regularization. ADMM has been applied to solve sparse coding problems efficiently.

Matching pursuit algorithm

Init : Residual $R = I$, sparse vector $a$ such that $\forall i$, $a[i] = 0$
while $\frac{1}{2} \sum_{x, y} R[x, y]^2 > \vartheta $, do :

Matching pursuit algorithm

Init : $R = I$, $\forall i$, $a[i] = 0$
while $\frac{1}{2} \sum_{x, y} R[x, y]^2 > \vartheta $, do :
- compute $c[i] = \sum_{x, y} (R[x, y] - a[i] \cdot \phi[i, x, y])^2$
- Match: $i^\ast = \arg \min_i c[i]$

Matching pursuit algorithm

Init : $R = I$, $\forall i$, $a[i] = 0$
while $\frac{1}{2} \sum_{x, y} R[x, y]^2 > \vartheta $, do :
- Match : $i^\ast = \arg \max_i \sum_{x, y} R[x, y] \cdot \phi[i, x, y]$

Matching pursuit algorithm

Init : $R = I$, $\forall i$, $a[i] = 0$
while $\frac{1}{2} \sum_{x, y} R[x, y]^2 > \vartheta $, do :
- Match : $i^\ast = \arg \max_i \sum_{x, y} ( I[x, y] \cdot \phi[i, x, y])$
- Assign : $a[i^\ast] = \frac{\sum_{x, y} R[x, y] \cdot \phi[i^\ast, x, y]}{\sum_{x, y} \phi[i^\ast, x, y] \cdot \phi[i^\ast, x, y]}$

Matching pursuit algorithm

Init : $R = I$, $\forall i$, $a[i] = 0$, and normalize $\sum_{x, y} \phi[i, x, y]^2 = 1$
while $\frac{1}{2} \sum_{x, y} R[x, y]^2 > \vartheta $, do :
- Match : $i^\ast = \arg \max_i \sum_{x, y} R[x, y] \cdot \phi[i, x, y]$
- Assign : $a[i^\ast] = \sum_{x, y} R[x, y] \cdot \phi[i^\ast, x, y]$

Matching pursuit algorithm

Init : $R = I$, $\forall i$, $a[i] = 0$, $\sum_{x, y} \phi[i, x, y]^2 = 1$
while $\frac{1}{2} \sum_{x, y} R[x, y]^2 > \vartheta $, do :
- Match : $i^\ast = \arg \max_i \sum_{x, y} R[x, y] \cdot \phi[i, x, y]$
- Assign : $a[i^\ast] = \sum_{x, y} R[x, y] \cdot \phi[i^\ast, x, y]$
- Pursuit : $R[x, y] \leftarrow R[x, y] - a[i^\ast] \cdot \phi[i^\ast, x, y]$

Matching pursuit algorithm

Init : $R = I$, $\forall i$, $a[i] = 0$, $\sum_{x, y} \phi[i, x, y]^2 = 1$
compute $c[i] = \sum_{x, y} R[x, y] \cdot \phi[i, x, y]$
compute $X[i, j] = \sum_{x, y} \phi[i, x, y] \cdot \phi[j, x, y]$
while $\frac{1}{2} \sum_{x, y} R[x, y]^2 > \vartheta $, do :
- Match : $i^\ast = \arg \max_i c[i]$
- Assign : $a[i^\ast] = c[i^\ast]$
- Pursuit : $c[i] \leftarrow c[i] - a[i^\ast] \cdot X[i, i^\ast] $

[LP (2004)]

Matching pursuit algorithm

Code @ A hitchhiker guide to Matching Pursuit

Matching pursuit algorithm

Hebbian learning (once the sparse code is known):

$$ \phi_{i}[x, y] \leftarrow \phi_{i}[x, y] + \eta \cdot a[i] \cdot (I[x, y] - \sum_{i=1}^{K} a[i] \cdot \phi_{i}[x, y] ) $$

[LP (2015)]

Matching pursuit algorithm

Sparse representations in a nutshell

Convolutional Sparse Coding

[[Boutin *et al*, 2021](https://laurentperrinet.github.io/publication/boutin-franciosini-chavane-ruffier-perrinet-20/)] — [Boutin *et al*, 2021]

Convolutional Neural Nets (CNN)

[[Jérémie & LP, 2023](https://laurentperrinet.github.io/publication/jeremie-23-ultra-fast-cat/)] — [Jérémie & LP, 2023]

Convolution: Mathematics

One-dimensional discrete convolution (eg in time) with a kernel $g$ of radius $K$: $$ (f \ast g)[n]=\sum_{m=-K}^{K} f[n-m] \cdot g[m] $$

Convolution: Mathematics

Convolution of an image (two-dimensional) with a kernel $g$ of radius $K\times K$:

$$ (f \ast g)[x, y] = \sum_{i=-K}^{K} \sum_{j=-K}^{K} f[x-i, y-j] \cdot g[i, j] $$

Convolution: Mathematics

Cross-correlation of an image (two-dimensional) with a kernel $g$ of radius $K\times K$:

$$ (f \ast \tilde{g})[x, y] = \sum_{i=-K}^{K} \sum_{j=-K}^{K} f[x+i, y+j] \cdot g[i, j] $$

Convolution: Mathematics

[[Amidi & Amidi](https://stanford.edu/~shervine/teaching/cs-230/cheatsheet-convolutional-neural-networks)] — [Amidi & Amidi]

Convolution: Mathematics

Correlation of an image defined on several channels (note the order of the indices):

$$ (f \ast \tilde{g})[x, y] = \sum_{c=1}^{C} \sum_{c,i,j} f[c, x+i, y+j] \cdot g[c, i, j] $$

Convolution: Mathematics

Correlation of a multi-channel image for multiple output channels (note the order of the indices):

$$ (f \ast \tilde{g})[k, x, y] = \sum_{c,i,j} f[c, x+i, y+j] \cdot g[k, c, i, j] $$

CNN: the HMAX model

[[Serre and Poggio, 2006]](https://biology.stackexchange.com/questions/10955/ventral-stream-pathway-and-architecture-proposed-by-poggios-group) — [Serre and Poggio, 2006]

CNN: challenges

Convolutional Sparse Coding

Code @ A hitchhiker guide to Matching Pursuit

Convolutional Sparse Coding

[[LP, 2015](https://laurentperrinet.github.io/publication/perrinet-15-bicv/)] — [LP, 2015]

Code @ SparseEdges

Convolutional Sparse Coding

[[Ladret *et al*, 2024](https://laurentperrinet.github.io/publication/ladret-24-sparse/)] — [Ladret *et al*, 2024]

Convolutional Sparse Coding

CNN: Predictive processing

CNN: Topography

CNN: Topography

Sparse representations

Laurent Perrinet

NeuroSchool PhD Program in Neuroscience

[2025-03-11]

$logo$

Code / Contact me @ laurent.perrinet@univ-amu.fr