naires et non pondérées. Cependant, ce modèle ne répond pas complètement à la forte contrainte de parcimonie que doit satisfaire le "codage neural". Afin d'aller plus loin dans le sens de la parcimonie, le réseau proposé dans [GB11] doit être repensé et réévalué en ce qui concerne l'utilisation des ressources disponibles : les messages à y stocker ne doivent pas utiliser toutes les grappes du réseau mais seulement une partie d'entre elles. Le type de réseau proposé dans cette thèse est donc une extension de celui présenté dans [GB11] pour lui conférer de plus fortes catactéristiques de parcimonie. Ce nouveau réseau offre une capacité de stockage importante et un fort pouvoir de correction de messages erronés ou partiellement effacés. La diversité, c'est-àdire le nombre de messages pouvant être mémorisés, est proportionnelle au carré du nombre total de noeuds, alors que dans le modèle classique, elle est proportionnelle au carré du nombre de noeuds dans chaque grappe. Par ailleurs, il a été constaté et démontré que, pour une même diversité, le taux d'erreur dans la récupération de messages tronqués est considérablement plus bas avec le réseau que nous proposons qu'avec le réseau classique. En outre, nous pensons que la structure et les principes de mémorisation de ce nouveau réseau sont plus proches de ceux du néocortex humain. Dans celui-ci, les micro-colonnes sont regroupées en colonnes à leur tour réunies en macro-colonnes. Dans notre modèle ainsi que celui décrit dans [GB11], les noeuds matérialisent les micro-colonnes qui sont regroupées dans des grappes représentant les colonnes et finalement toutes les grappes forment le réseau représentatif d'une macro-colonne. La différence réside dans l'utilisation des grappes, bien plus parcimonieuse dans notre cas, et donc plus plausible biologiquement.

En plus de sa grande capacité de stockage ainsi que de sa forte aptitude à la correction, les algorithmes d'écriture et de récupération de messages sont simples.

Ce modèle est un bon candidat pour expliquer les mécanismes et les principes de la mémoire cérébrale à long terme et aussi pour servir de point de départ dans

Résumé

Le principe de parcimonie, si fondamental dans les systèmes biologiques du fait de ressources limitées, peut être exploité avec profit dans la conception de systèmes efficaces de stockage de l'information. La parcimonie est une contrainte; malgré cela, les systèmes biologiques -le cerveau en premier lieu -sont complexes, puissants et flexibles. Le principe de parcimonie appliqué au traitement des signaux et des données peut donc conduire à des solutions efficaces dans l'acquisition et le stockage d'informations. Cette thèse traite de la conception d'un système neuroinspiré dont une des qualités recherchées est la parcimonie. Le système développé et validé est un réseau de neurones binaire et récurrent, analysé en détail dans le deuxième chapitre.

Le néocortex est la couche la plus récemment développée du cerveau humain et est le centre des pensées conscientes et du langage. Cette partie du cerveau présente donc un grand intérêt, en tant que référence biologique, dans la recherche de nouvelles solutions de mémorisation. Les premier et deuxième chapitres du mémoire de thèse proposent une courte analyse des caractéristiques et des modèles de la mémoire humaine et constituent une introduction à un réseau de neurones de stockage original exploitant le principe de parcimonie. L'organisation et les propriétés du néocortex ont conduit Gripon et Berrou à proposer un nouveau type de réseau de neurones [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF]. Ce réseau est constitué de noeuds regroupés en différents sous-ensembles disjoints appelés "grappes". Il lui correspond donc un graphe multiparti dont les connexions sont purement bi-1 la conception de machines capables de stocker un nombre considérable de messages, souvenirs, situations, voire même de séquences. Nos travaux ont fait l'objet d'une soumission d'article à IEEE trans. on Neural Networks and Learning Systems [START_REF] Aliabadi | Learning sparse messages in networks of neural cliques[END_REF].

Dans le troisième chapitre, le réseau est analysé sous l'éclairage de la théorie de l'information et du codage. Le réseau s'appuie en effet sur des lois de codage redondant qui lui confèrent des propriétés de codage correcteur d'erreurs ou d'effacements.

Ainsi il peut restituer un mot de code (un message) stocké à partir d'une version erronée présentée à son entrée. Les mots de codes linéaires, qui sont communément utilisés dans les systèmes de communication, dépendent d'une matrice génératrice.

Le réseau de neurones, quant à lui, résout le codage de canal différemment: les mot de code ne sont pas nécessairement linéaires. Le réseau est en effet capable de stocker une série de mot de codes (par exemple, un ensemble de messages indépendants et uniformément distribués) qui peuvent être ou ne pas être linéairement dépendants les uns des autres, ce qui laisse au concepteur un important degré de liberté dans le choix du transcodage (le "mapping" des informations et des noeuds du réseau). Le concepteur peut donc fixer les paramètres en fonction des exigences du système. Il existe deux principales différences entre le réseau classique et le réseau proposé dans cette thèse quand ils sont utilisés pour des applications de codage de canal. Dans le modèle classique, le nombre de mots de code possibles est très large en comparaison du nombre de messages stockés.

Dans le nouveau réseau, la diversité est beaucoup plus importante et est donc plus proche de la cardinalité des codes linéaires. Le deuxième avantage du nouveau réseau est la variabilité de la longueur des messages stockés. Cette dernière propriété rend le système capable d'exploiter des codes à longueur variable (quand les mots de code sont de différentes longueurs). Le système pourrait également réaliser une fonction de codage à taux de codage variable selon la qualité des canaux de communication.

Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF] suggérait que le codage de source et le codage de canal soient considérés comme des opérations de traitement de l'information distincts et disjoints. Des recherches ultérieures ont montré qu'un codage conjoint source canal pouvait améliorer les performances. Le réseau considéré dans cette thèse met en oeuvre un type de codage conjoint source canal qui est élaboré de la façon suivante.

Les messages sont stockés dans des cliques qui sont des sous-graphes entièrement connectés par des arêtes binaires. Considérons un message avec c sous-messages significatifs (non-zéro) stockés dans un réseau de χ grappes et ℓ noeuds dans chaque grappe (n = χℓ est le nombre total de noeuds). Le message est associé à une clique avec c 2 = c(c -1)/2 connexions binaires. Le message contient c log 2 ℓ bits. Ainsi, pour obtenir un effet de compression, l'inégalité c-1 2 < log 2 ℓ doit être respectée. Par ailleurs, une clique a une structure redondante, c'est-à-dire que les c noeuds appartenant à un message sont liés par c(c-1) 2 connexions alors que ⌊ c+1 2 ⌋ connexions peuvent être suffisantes pour spécifier tous les noeuds de la clique.

Du fait de cette redondance, une clique peut être considérée comme un mot de code d'un code redondant. On voit donc que, sous certaines conditions, codage de source et codage de canal peuvent être combinés dans une même opération de mémorisation dans le réseau.

La principale contribution de ce chapitre est le calcul des contraintes sur les paramètres du système, comme par exemple le nombre maximum de messages stockés et le nombre maximum acceptable de sous-messages manquants dans un message d'entrée. Ces contraintes sont calculées à l'aide de la théorie de l'information. Pour cela, la mémoire du réseau de neurones réalisant le stockage et le processus d'extraction est modélisé comme un canal de communication bruyant. L'ensemble de messages à stocker provient de la source de l'information et peut ensuite être récupéré à partir du message partiels. L'information est mesurée La structure CS est très similaire à la Bidirectional Associative Memories (BAM) proposée par Kosko et al., où un ensemble de paires de vecteurs de dimensions différentes est stocké dans un réseau à mémoire. Les systèmes de CS ainsi que leurs connexions avec les réseaux de neurones à mémoire et les techniques d'apprentissage automatique sont discutés dans ce chapitre. La principale contribution en est le calcul de conditions de récupération plus strictes que l'état de l'art sur ce genre de systèmes. Une condition de récupération originale est aussi obtenue pour des signaux approximativement parcimonieux.

Preface

Parsimony in biological neural systems such as the brain inspires the design of systems that may be more efficient. Indeed, parsimony in signals can be exploited for efficient sampling and storage. In this thesis the design of a biologically inspired system that employs parsimony of signals is the main subject of study. This system is a neural network memory which is presented in chapters two and three. At first, the parsimonious features of the human neocortex and the human memory are briefly investigated from psychological and biological aspects. These features have inspired a neural network memory introduced by Gripon and Berrou. An extension to this network is proposed in this thesis. It has more embedded sparsity features of the human brain in comparison with the classical network. It is also capable of storing sparse messages unlike this classical network. The proposed network is analysed and its advantages are brought to the fore. In chapter three, the proposed network is analysed from information and coding theory aspects. The network can be considered for error correction because it is an auto-associative memory and can therefore store a set of codewords (as messages) and recover them from distorted versions. The network implements a kind of joint source-channel coding which is elaborated in this part. The main contribution of the information-theoretic analysis is the computation of constraints on the system parameters, such as the maximum number of stored messages and the maximum number of acceptable missing sub-messages in a partial message.

In the fourth chapter, a new sparse signal acquisition technique namely com-8 pressed sensing is studied, exploiting information theory. Compressed sensing systems and their connection to neural network memories and machine learning techniques are discussed. The main contribution of this chapter is the computation of tighter information-theoretic recovery conditions on these systems. A novel recovery condition is also derived for approximately sparse signals.

CONTENTS

List of Tables

Chapter 1 Introduction

The brain is the most complex organ of the human body and the center of the nervous system. Although the brain has been studied for a long time from different aspects, such as philosophy, biology and psychology, it remains largely a mystery.

Among the revealed properties of the brain, computational capabilities, power efficiencies and enormous memory capacity of the brain are the most significant features to the information technology community. Evolution has made the brain a powerful computing and reasoning machine. It has also evolved to a power efficient system that consumes only 10 -16 joules per operation per second, whereas modern computers consume up to 10 10 times more energy [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF].

The elements of the brain are distributed parallel processors, resulting in significant computational power. Neural computations take place in millisecond-scale, whereas semiconductor circuits perform nanosecond-scale operations. Today, semiconductor circuits have reached a critical point: to increase the processing speed, the clock frequency has to be increased. A higher clock frequency requires smaller components and circuits but the circuits can be shrunk only up to a certain limit.

To speed up processing, another possibility is to increase the number of transistors, which increases the power consumption. This leads to heat production in a small area and the electronic circuit can work in a limited temperature range. This 20 CHAPTER 1. INTRODUCTION is where the importance and power of the biological neural systems become more evident. Although they are slow at micro operations (in neurons, dendrites and axons), they have remarkable performance when it comes to complicated processing tasks, such as image processing [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. Modern computers may use biological parallelism features to overcome their circuitry limitations.

The capability of learning and generalizing is a property of the biological neural networks. The human brain learns an enormous amount of information through input stimuli and it is then able to respond to the stimuli that were learned before.

The brain may also compute a response to a stimulus without knowing the direct answer by inferring from what has been learned. This is a desirable feature to be implemented in man-made machines [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF].

The brain has been divided anatomically and functionally into many regions.

The one which is of our main interest throughout this report is the neocortex, which is also known as the grey matter. It is the 2 to 4 mm thick outermost layer of the cerebral hemispheres. This thin layer is the center for controlling physical movements, emotions, and reception and perception of vision, auditory, semantics, etc. Although there are many parts of the brain that are involved in what is called memory, we focus on this very recently biologically evolved region.

Memory

Memory in the human brain is the process of learning, storing and retrieving information [START_REF] Sandberg | Bayesian Attractor Neural Network Models of Memory[END_REF]. This process can be studied with respect to both biological and psychological aspects. The brain at the biological and circuitry levels is a connectionist network consisting of nodes (neurons) and connections (axons, dendrites and synapses) where information is stored in the connections [START_REF] Versace | The brain of a new machine[END_REF]. The connections are mostly built during the infancy. They change throughout the lifetime when the brain learns by being exposed to input stimuli. A simplistic model is that 1.1. MEMORY 21 the brain learns by loosening and strengthening its connections, which is known as synoptic plasticity.

The brain at the mental level is considered by psychologists and philosophers as a system with a set of sub-systems in which information is processed and stored.

From this point of view, learning, recovery, storage and decision-taking functions are treated abstractly without getting into cell-level operations. This phenomenon has been studied throughout history by philosophers such as Aristotle and psychologists [START_REF] Sandberg | Bayesian Attractor Neural Network Models of Memory[END_REF]. Ancient thinkers considered the memory as a storage space that keeps information without processing capability. Aristotle believed that the outside world leaves imprints on the brain in the mental matter. He modeled memory as a function that also connects the content of the mental matter rather than just a storage unit [START_REF] Sandberg | Bayesian Attractor Neural Network Models of Memory[END_REF]. This rather old perception of human memory has influenced our knowledge of memory even today. It is known now that memory and processing are not two distinct functions of the brain but rather are of the same process [START_REF] Versace | The brain of a new machine[END_REF].

There are two modern psychological memory models to explain the mechanisms of the human memory. These are the Atkinson-Shiffrin [START_REF] Atkinson | Human memory: A proposed system and its control processes[END_REF] the importance of each stage, it is worth noting that the storage in LTM requires perception of the items in early stages of SM and STM. Thus, storing an item in the long-term memory (which we refer to in everyday life as memory) is a process CHAPTER 1. INTRODUCTION rather than isolated operations. In this report, the memory is a system that captures a set of input information (through input stimuli) and is able to retain (for a long time) and reuse it.

Retrieval of stored information is a part of a memory system. In the brain, retrieval is carried out in different forms which are categorized into recall and recognition [START_REF] Sandberg | Bayesian Attractor Neural Network Models of Memory[END_REF]. Recall is the ability to retrieve what was learned by giving a hint. Recognition is the ability to acknowledge what was learned in the past [START_REF] Sandberg | Bayesian Attractor Neural Network Models of Memory[END_REF]. These are two fundamental functions of the memory that are also considered in the design of artificial memories. A memory that is exploited as an associative memory carries out a recall function. In set implementation applications, one needs to know if an element is already in a set to decide whether the element should be added to the set or not. This is what is called recognition.

The recall function has three types, namely free recall, cued recall and serial recall. Free recall is when the memorized items are retrieved without their order. Cued recall is the retrieval of an item through another item, where the items in question were learned in a pair or a group. Serial recall is the retrieval of items in the order that they were learned.

Compression and Robustness

The brain is a complex system including information processing and storage subsystems. It is known that the brain is capable of storing a large amount of information with fairly acceptable retrieval accuracy [START_REF] Wang | Discovering the capacity of human memory[END_REF]. To accomplish this, it requires that the information is stored efficiently with a mechanism to assure the robustness of recovery. An efficient storage strategy is one that requires the fewest memory to hold information content, which is known as compression. On the other hand, information retrieval is robust if there is redundancy to make error detection and correction possible. Reliability at the circuitry and biological level is obtained by 1.3. ARTIFICIAL NEURAL NETWORKS 23 creating multiple paths between neurons. Therefore, if neurons lose part of their connections, the brain is still able to recover at least part of what has been learned.

Neural Coding

The brain receives an enormous amount of the sensory information from outside such as visual stimuli and from inside which are thoughts (as a product of thinking and imagination) [F 02]. This information is crude and needs to be prepared in a form that the brain is capable of perceiving and storing. It is transformed into electrical signals and chemical reactions which neurons, axons, dendrites and synapses are capable of handling. Moreover, information is also organised in the brain in a way to be efficiently processed and stored, rather than to be treated as a pile of random data. This requires a system that projects stimuli. The neural code is the way that the stimuli information is projected into the brain [START_REF] Borst | Information theory and neural coding[END_REF].

Artificial Neural Networks

Artificial neural networks are an effort to build systems that mimic biological neural systems, in order to exploit the capabilities and power of their architecture. These capabilities are parallel computation, adaptivity, and the ability to learn and generalize [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. In this work, an artificial neural system is proposed to model the human neural system, which has the brain as the center of the nervous system.

The nervous system may be seen in three parts. Receptors convert stimuli into electrical signals to be sent to the brain. This process is represented as the neural network in Fig. 1.1. The effectors in the nervous system convert the electrical signals received from the brain into system responses [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. In Fig. 1.1, the arrows show that the communication between the brain and receptors and effectors is bidirectional.

There are two kinds of neural networks, namely feedforward networks and recur- is the ability of the network to retrieve the stored information correctly. Both of these characteristic are defined and elaborated in detail in the following chapter for the specific network that is considered in this report.

Thesis structure

Chapter 2 The proposed neural network memory that is capable of storing sparse messages is presented. The network is analysed and compared with the classical network from which it has been derived. It is shown that the proposed network improves significantly the maximum number of stored messages when the messages are strongly sparse.

Chapter 3 The proposed neural network is investigated from information-theoretic aspects. It can be exploited for channel coding applications and the network itself can be considered as a joint source-channel coding system. The network is then analysed using Fano's inequality from which a set of recovery constraints are derived.

Chapter 4 Recovery conditions for Compressed-Sensing (CS) are the subject of this chapter. It is mainly used for dimensionality reduction which is also a topic of machine learning and neural networks. CS is studied exploiting information theory, through which a few tight sufficient recovery conditions are computed.

Chapter 2

Sparse Neural Network Memories

In this chapter, an artificial neural network based on the human neocortex structure is presented. This network embodies several features of the biological neural systems and more specifically of the neocortex in its design.

The brain comprises neurons, dendrites, axons and synapses as its main material and other cells such as glial cells for the metabolic support (although this may seem oversimplified). They construct a grid network with neurons as its nodes and, dendrites, axons and synapses as its connections [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. This structure is well recognised in mathematics and computer science as a graph. Hereafter, the artificial neural network is considered as a graph consisting vertices and edges.

In [START_REF] Mcculloch | A logical calculus of the ideas immanent in nervous activity[END_REF][START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF] vertices represent neurons and edges represent dendrites, axons and synapses. Although the graph representation of neural networks is adopted in this document, the notion of vertices and edges is different. More specifically, the vertices represent a group of neurons which is explained in the following section.

The principle difference between mathematical graphs and neural networks are the underlying dynamics of the neural networks: the connections (edges of the graph) and nodes (vertices of the graph) in a neural network may change due to 30 CHAPTER 2. SPARSE NEURAL NETWORK MEMORIES the effect of input stimuli from time to time [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. This resembles the living tissues and cells in the human brain. That turns the brain into an evolving and self-organising organ rather than a solid connected grid. The way that the vertices of a neural network are organised and connected has a profound effect on its performance and efficiency. To obtain a network with a desirable performance and efficiency, we refer to the brain that has evolved towards, efficiency throughout time.

In the human brain, the most recently developed part, the neocortex, is of our interest. The neocortex is a well structured layer of the brain and it is the center of conscious thoughts and language. The human neocortex has inspired the development and design of the network (in this document) that is sparse of different levels.

The basic structure of the proposed network is based on the network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF].

This is adopted and extended in this document to store sparse data structures.

Sparse Coding

The notion of sparsity appears in different forms in the biological neural systems.

The very first stage of sparsity in the brain is at the reception of numerous input stimuli. The neural systems are selective when they are exposed to the input stimuli. They do not capture every stimulus but a few at a time [START_REF] Miller | The magical number seven, plus or minus two: some limits on our capacity for processing information[END_REF]. This can be observed in the daily life where we always capture those information that we intend to. For example we are able to concentrate on a specific person's voice in a crowd. This can also be unconscious where much of the sensory information received by our skin is automatically neglected by the brain but those that are significant such as pain. The perceived information are passed to SM and STM afterwards (see section 1.1) to be noticed by the conscious mind. They are passed to a deeper memory level, LTM, depending on whether they need to be remembered

SPARSE CODING

later. This structure acts as a biological sieve that filters out the unnecessary information.

The second sparsity feature is observed in the organization of neurons and connections. The neural system is organized in different sections and the neocortex is not an exception, in its both vertical and horizontal dimensions. It has six horizontal layers containing various types of the neurons and other vital cells. The one with greater importance in this report is columnar division of the neocortex [START_REF] Mountcastle | The columnar organization of the neocortex[END_REF]. A column from top-down perspective is a cylinder containing a group of neurons with the same receptive field. In a column, there are microcolumns1 that are groups of about 80 ∼ 100 neurons [START_REF] Mountcastle | The columnar organization of the neocortex[END_REF]. They are believed to be the basic units of the neocortex [START_REF] Mountcastle | The columnar organization of the neocortex[END_REF]. The microcolumns are connected through horizontally organized neural layers which constructs a grid [START_REF] Mountcastle | The columnar organization of the neocortex[END_REF]. A single neuron has a simple structure that may not be able to store and process a remarkable amount of information. Thus, a stand alone neuron is not sufficiently informative, which implies that the complicated operations in the brain require a developed organization of neurons. This has led the brain to evolve into a structure in which the stored information in the neocortex appears as activated microcolumns that are connected horizontally [F 02]. These connections are locally dense and recurrent whereas they are sparse at the global level [START_REF] Sandberg | Bayesian Attractor Neural Network Models of Memory[END_REF].

The brain stores information that is received from the environment and its internal state (e.g. thoughts) in sparse patterns of simultaneously active microcolumns. This theory is called "neural coding" (see section 1.2.1) [START_REF] Averbeck | Neural correlations, population coding and computation[END_REF]F 02].

This sparse representation of information, i.e., neural coding is the feature that is exploited in the neural network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] and even more in this report. is depicted in which the number of fanals in each cluster is equal to a constant.

This model is further developed and analysed in the following sections as a neural network memory for which the network dynamics and its properties will be given.

Messages

Information in digital devices is quantized and packed into groups of bits and bytes, etc. In this report, information is represented with vectors in which the elements are drawn from an alphabet. The vectors can be the product of sampling real-world analog information or they may be obtained by the post processing of an informa- There is an image (in the image set) to be recognized when a part of it is covered or missing. This requires a post-processing framework that extracts unique image specifications which are stored (in the neural network memory) and used as the image signature. A modified Speeded Up Robust Features (SURF) [START_REF] Bay | Speeded-up robust features (SURF)[END_REF] or Scale-Invariant Feature Transform (SIFT) [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] may be applied on images to get the images' specifications. These transforms return a set of pixel coordinates as a set of interest points, also known as keypoints. For each image with χ pixels, a vector (of size χ) is constructed in which the keypoints take a nonzero value and the rest are zero. It is assumed that these vectors uniquely represent each image in the image set are sparse and they are so-called specification vectors. Specification vectors are stored in the proposed network. When part of an image is missing, it appears as missing nonzero elements in its corresponding specification vector. The defected image is then recognized by feeding the network with its partially known specification vector and using the properties of the associative memory especially redundant coding.

Another application is wireless communications. A technique so-called Cogni-

tive Radio [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF] is the center of attention among the researchers of the field in recent years. Communication spectrum is a limited and therefore expensive resource. This gets worse by the advent of new wireless hand-held and personal communication devices. In the past, organisations such as International Telecommunication Union (ITU) allocated communication bandwidths to many standards, especially mobile networks. Today, there is almost no more free-space left in the frequency spectrum. This has led the communications bodies to allocate shared bandwidths for various applications such as personal communications. There are various strategies to use shared radio spectrum bandwidths. One of the cognitive radio techniques is the opportunistic scheme through which radio devices access randomly the spectrum range. The issue that rises with this opportunistic scheme is that each radio device is responsible for surveying the frequency spectrum to find an empty slot (in time, frequency and space) for communication. Therefore, a radio device sees the frequency spectrum as a vector in which the occupied frequency slots appear as nonzero elements and the rest is zero. This vector is named here as spectrum state vector. In hand-held and battery-driven devices, energy is a valuable asset to be conserved for vital operations. Assume the spectrum changes among a limited number of patterns for a period of time. In this case the device may fully sense the spectrum and store the spectrum state vector in the proposed network (as an associative memory). Afterwards, the radio device may increase its energy efficiency and communication rate by sensing a limited part of the whole spectrum and recover the rest from the neural associative memory.

The basic item which the network perceives as an input stimulus is a message.

Following the above discussion, a message with a few information bearing elements is so-called sparse. The sparse messages that are dealt with in this report can be either naturally sparse or result of a transform such as Fourier and Wavelet. In this report, the sparse messages are treated by the network regardless of their real-world source and they may belong to one of the mentioned or other possible applications.

A message is a vector with χ elements. An element of the message is so-

STORAGE

35

called sub-message that is drawn from an alphabet denoted by A or it may be blank. The blank elements are the none information-bearing elements because they are null or negligible. The number of non-blank (significant) sub-messages is so-called message order. The sub-message alphabet has finite cardinality |A| = ℓ.

Throughout this report, sub-messages are assumed to be uniformly distributed over the alphabet A. Although the alphabet size can be arbitrary depending on the application, it is often a power of two. This choice makes the network compatible with the digital systems where information is quantized in bits. Therefore, a message may be considered as a sequence of bits to be stored in the network. This requires that the message is divided into c groups of κ = log 2 ℓ bits (see section 2.3).

Storage

Neural networks are connectionist networks composed of nodes and their corresponding connections. This structure can be modelled as a graph in which these nodes are vertices and their interconnections are edges of the graph [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF][START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF].

Throughout this document, a network with binary connections is considered; in other words, either there is a connection between two nodes or there is no connection. In the following, the network and its components that store messages according to the sparse coding approach are defined.

Definition 1 (Neural Network). According to the previously given theory, a neural network is an undirected multipartite2 graph (F 1 , ... , F χ , W) where F 1 , ... , F χ are sets of vertices and W is the set of edges. All sets of vertices have equal cardinality, ∀j ∈ {1, ... , χ}, |F j | = ℓ.

CHAPTER 2. SPARSE NEURAL NETWORK MEMORIES

Definition 2 (Cluster). A set of vertices F i ∈ {F 1 , ... , F χ } is a cluster. A cluster is indicated by an index and the set of cluster indices is C = {1, ... , χ}.

Definition 3 (Fanal). A vertex of the graph which is an element of ∪ χ i=1 F i is a fanal. A fanal in a cluster is indicated by an index. The set of fanal indices is

F = {1, ... , ℓ}.
A neural network is uniquely identified with (W, χ, ℓ) where ℓ is the number of fanals in each cluster and χ is the number of clusters in the network that is so-called afterwards cluster space size. A pair (i, j) ∈ C × F uniquely specifies a vertex in the graph.

The defined graph along with the storage and retrieval mechanisms is a network that is capable of interacting (with another system or the outside world through an interface) as a system. The very first step toward building such a system is the storage process that the storage efficiency depends on it. It also significantly influences the retrieval process, which will be elaborated in the next sections.

The storage is the process of mapping a set of messages into the network through constructing binary connections among the fanals. To exploit the network efficiently, a well designed storage procedure is required in which various goals are pursued. The first purpose of the storage is to map a message in the network by constructing or removing edges of the graph (connections) in a manner that the message could be retrievable afterwards. The neural network memory retrieves the stored message by providing its associated content (e.g. partial message or blurred/noisy message) to the network. This implies that the storage is a oneto-one function. This mapping may be considered one-to-one where only a single message is subject to storage and recovery in the network.

The efficiency of the storage is also an important issue along with the correct storage and retrieval of messages. In other words, the storage should exploit the intrinsic property of the network and the messages (e.g. sparsity) to perform a kind

STORAGE of compression (lossy or lossless)

. This is to avoid the storage of messages as a pile of information that would imply an inefficient use of resources. In this network, such a compression scheme is implemented by sharing fanals and connections among stored messages. This compression occurs where at least two distinct messages have a few corresponding equal sub-messages. For example consider two messages drawn from alphabet A = {1, 2, ... , 128} and dashes as blank sub-messages,

m 1 = [-, 21, -, -, 2, -, 12, -, 5, -, -, -, 115, -]
and

m 2 = [-, 45, -, -, 2, -, 12, -, -, 65, -, -, 74, -]
where the fifth and seventh sub-messages of these two messages are equal. These messages may be associated with two disjoint cliques in the network that share two fanals and a single connection. This has side effects on content addressability of the network where in some cases the network may not be able to recover the stored messages. It is due to the fact that the compression in this network is obtained by sharing network connections, that is, by a lossy compression (see [START_REF] Cover | Elements of Information Theory[END_REF]) in which a part of stored information may not be recovered. The storage is also aimed to embed a well designed redundancy to combat deficiencies in the network connections and the input stimuli (e.g. noisy and/or partial messages) at the retrieval. It was also mentioned that the compression in use in this network may result in weakening content addressability of the network. A smart redundancy is the answer to such negative effect. Above discussion refers to source coding (compression) and channel coding (embedded smart redundancy) in information theory that was studied and quantified for the first time by Shannon in [START_REF] Shannon | A mathematical theory of communication[END_REF]. This network will be studied from this perspective in the later sections and chapters of this report. The mentioned design criteria in the network are satisfied through construction of complete subgraphs. Assume there is a message to be stored. Each sub-message (from alphabet A) is mapped to its corresponding fanal (one of the ℓ fanals in the corresponding cluster). Then the message is stored by connecting all these fanals. This results in a complete subgraph for a message in the network3 . In Fig. 2.2 a clique, consisting of eight fanals and twenty-eight connections is depicted. The total number of connections in a bidirectional clique (of this

network) is c(c -1) 2 (2.1)
where c is the message order, that is also called clique order.

In this neural clique (a clique in the neural network), the fanals have more than a single connection to their neighbour fanals. This makes the network capable of retrieving the message where a few but not all sub-messages (and correspondingly fanals) are unknown which is a robustness feature.

(1,4) W (ρ) ={{(1, 4), (3, 7)}; {(1, 4), (6, 5)}; {(1, 4), (7, 3)};

(7,3) (6,5) (3,7)
{(3, 7), (6, 5)}; {(3, 7), (7, 3)}; {(6, 5), (7, 3)}}.

In this specific example, it is assumed that A = F , thus, the mapping is Identity function4 . It is also assumed (in this example and in this report) that the support5 of the messages are chosen uniformly random from χ c subsets of size c (the message order). Likewise, the storage of a message set involves repeating the same operations.

In the following, the storage process is formalized for the network with arbitrary cluster space size χ and number of fanals ℓ in each cluster. Assume a network (W, χ, ℓ) that stores a message set M. Then, the storage involves constructing connections' set W of the neural network from the message set.

Assume message m is subject to storage, a one-to-one function b maps each

non-blank message node m r ∈ m and m r ∈ A to a cluster index i ∈ C . b : A -→ C m r -→ i = b(m r ).
Function b is a one-to-one function, which guarantees that there is no more than only one activated fanal in the same cluster for a message. This is one of the conditions that enforces the sparsity of the network.

Next, a one-to-one mapping g maps each sub-message m r ∈ A to a fanal index f ∈ F .

g : A -→ F m r -→ f = g (m r ).
After assigning the clusters and fanals through b and g , function D pairs corresponding clusters and fanals of message m in a set.

D : m -→ {(b(m r ), g (m r )) : m r ∈ m}.
To store the message in the neural network, one-to-one function W maps ρ = D(m) to binary graph edges (network connections). It constructs a subgraph that involves graph vertices (fanals) in ρ,

W (ρ) = {{(i ′ , j ′ ); (i, j)} ∈ ρ × ρ : i = i ′ }.
Definition 4 (Neural Training of set M). Let m ∈ M be a message to be stored by the neural network. The training consists in setting the binary edges of graph

G = (F 1 , ... , F χ , W) as W = m∈M W (D(m)) = m∈M W (ρ).
(2.2)

It is worth mentioning that as the given storage procedure suggests, the sequence order of messages is not stored. The messages can be stored in any order and at any time or all at the same time.

Since b and g are one-to-one functions, it can be directly deduced that W is also a one-to-one and reversible function. Assume any two messages m and m ′ that hold m = m ′ . This implies that we have

W (D(m ′ )) = W (D(m)).
The connections' set of W can be alternatively represented as a four dimensional matrix This way of representing network connections results in saving memory. Moreover, it simplifies the description of recovery algorithms that are explained in the following section.

w (i ′ j ′ )(ij) =    1 if {(i ′ , j ′ ); (i, j)} ∈ W, 0 otherwise, (2.3
Previously in this section, the storage procedure in the network was spelled out. The design and study of the network requires to formalize it with measurable quantities. These quantities are employed to optimize the network from different aspects. In the following, first the network is considered to store messages of length χ with constant number of significant (non-blank) sub-messages c and afterwards it is extended to the storage of messages with variable number of significant submessages.

The connections among fanals are binary from which the total number of storage bits in the network can be deduced as

Q = χ(χ -1)ℓ 2 2 (2.4)
that is the number of potential bidirectional connections. This quantifies the maximum number of available bits and it may not be confused by the maximum number of stored bits (which is always less due to redundancy).

In graph theory, the edge density is used to study the average connectivity of the graph nodes. It is the ratio of the number of edges to the total number of possible edges in the graph [START_REF] Diestel | Graph Theory[END_REF]. Assume a single message of order c is stored, then the network density is c(c-1) χ(χ-1)ℓ 2 . It is the ratio of the number of edges in a clique with c nodes in (2.1) to the total number of possible connections given by (2.4). The network connections after the storage of a large number of messages are considered asymptotically i.i.d. and uniformly distributed. This results in the probability of having a connection between two fanals of distinct clusters being approximately equal to the network density. Assume M i.i.d. and uniformly distributed messages are stored. The network density becomes:

d = 1 -1 - c(c -1) χ(χ -1)ℓ 2 M (2.5)
where c is the message order and χ is the cluster space size. Reversely, the number of stored messages as a function of the network density is

M = log(1 -d) log 1 -c(c-1) χ(χ-1)ℓ 2 . (2.6)
In Fig. 2.4 the evolution of the network density as a function of M is shown where χ = 100 and ℓ = 64. A network with a density close to unity may not recover the stored messages. As a result, a low density network is often desired. It can also be

STORAGE

concluded that since the network density grows slower for smaller message orders, the network is capable of storing more messages. In other words, the number of stored messages is proportional to the sparseness of messages. + c log 2 (ℓ) bits in the network. For M messages, the network stores

B = M log 2 χ c + c log 2 (ℓ) (2.7)
bits of information. The first logarithm is the number of bits required to store non-blank cluster indices and the second logarithm is the number of bits required to store the non-blank elements' values. The efficiency of the network is defined as the ratio of the number of stored bits to the number of total storage bits

η = B Q = M log 2 χ c + c log 2 (ℓ) 0.5χ(χ -1)ℓ 2 . (2.8) CHAPTER 2.

SPARSE NEURAL NETWORK MEMORIES

The efficiency is a metric without dimension that varies between 0 and 1: 0 ≤ η ≤ 1. It may be used to measure the amount of redundancy for a stored set of messages.

Efficiency η = 1 occurs where all the network connections have been used to store a message set (i.e. there is no redundancy in the network). Diversity is defined as the maximum number of messages that the network is capable to store.

This occurs when η = 1,

M max = χ(χ -1)ℓ 2 2 log 2 χ c + c log 2 (ℓ)
.

(2.9) Fig. 2.5 illustrates the efficiency-1 diversity in (2.9) for several values of ℓ and for a network with cluster space size χ = 100. It can be observed that a network with higher number of fanals in each cluster and higher sparsity level (i.e. lower message order) has larger diversity. The tail of all curves ends at c = χ, that is

STORAGE

when the messages are no longer sparse. This point has the lowest diversity for specific ℓ and χ.

Diversity is an important measure when the network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] is compared with the proposed network. Indeed, diversity is improved with respect to the one in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] M max = 0.5(c -1) ℓ 2 log 2 ℓ

(2.10) while the proposed network has a diversity6

M max = Ω χ 2 ℓ 2 log 2 (χℓ)
.

The latter depends on the total number of fanals n = χℓ whereas in (2.10), diversity only depends on the number of fanals ℓ (because the number of clusters is constant and it is equal to the message order). Therefore, the proposed network has significantly improved the diversity. On the other hand, since the network does not store the blank sub-messages, it exploits the network resources efficiently. This results in increasing the number of stored messages compared to the classic network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF].

Now, the storage of messages with variable number of significant sub-messages is considered. Assume messages set M in which the messages have c min ≤ c ≤ c max significant number of sub-messages. The number of messages with order c is indicated by M c . the density of the network that stores this variable order message set is

d = 1 - cmax c=c min 1 - c(c -1) χ(χ -1)ℓ 2 Mc .
(2.11)

In this report, it is assumed that the message order c min ≤ c ≤ c max is uniformly distributed between c min and c max . Therefore, the number of messages with order

c is M c = M/(c max -c min + 1) when M is large [Pap91]. The binary information borne by a message m ∈ M is log 2 χ c m + c m log 2 (ℓ),
where c m is the number of significant sub-messages of message m. Efficiency is equal to

η = 2 m∈M log 2 χ c m + c m log 2 (ℓ) χ(χ -1)ℓ 2 (2.12)
when the message orders are uniformly distributed between c min and c max , this becomes

η = 2M cmax c=c min log 2 χ c + c log 2 (ℓ) (c max -c min + 1)χ(χ -1)ℓ 2 .
(2.13) Network diversity as it was computed before in (2.9) by setting η = 1, is

M max = (c max -c min + 1)χ(χ -1)ℓ 2 2 cmax c=c min log 2 χ c + c log 2 (ℓ)
.

(2.14)

In this section, the essential parameters to evaluate and optimise the network were given. Indeed, the network can be characterized by its density, d, diversity, M max , and content addressability metrics such as successful retrieval probability.

The retrieval probability and its computation will be discussed in the following sections of this chapter.

Retrieval

A biological neural system such as the human brain is exposed to the input stimuli during the learning process. These stimuli create or change the connections' strengths, which is the act of learning. Thereafter, the brain is able to retrieve these stimuli in various scenarios. An example of this is the capability of storing and reading the written words. For example, the brain stores a word (spell of the word) which afterwards it is able to remember completely even if it is given a part of it (a few but not all letters of the word) [START_REF] Perfetti | The brain might read that way[END_REF]. The proposed neural network memory, inspired from the human brain, is expected to perform similar functionality. It is though limited to the storage of a message set that can be considered as words of a dictionary (similar to human experience of learning and remembering words). The messages (in the message set) consist of sub-messages taken from an alphabet (similar to a language alphabet like English alphabet).

This network is expected to be able to retrieve a stored message from its partially known sub-messages which is the fundamental property of associative memories. The network also addresses the problem where a hypothetical message is to be verified by the network whether it is stored. This is is also known as Set

Implementation. The brain is also able to recognize morphological or dictation errors. Such situations can take place for example when the letters of a written word are permuted [START_REF] Grainger | Does the huamn mnid raed wrods as a wlohe?[END_REF]. The network is capable of retrieving a message where it is fed by its permuted sub-messages.

The classical retrieval algorithm was first introduced in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF]. The retrieval algorithm is based on a variation of Winner-take-all (see [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF][START_REF] Maass | On the computational power of winner-take-all[END_REF]) and message-passing. The employed message-passing is similar to a kind of messagepassing used in error control coding. In the following, the retrieval algorithm given in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] is elaborated. Although the principles of the algorithm remain unchanged, it is modified in different ways to improve the performance in terms of retrieval error probability.

Winner-take-all

Winner-take-all (WTA) is a nonlinear operation in the human brain that is also adopted in artificial neural networks. It brings significant flexibility and capability to neural networks [START_REF] Maass | On the computational power of winner-take-all[END_REF]. The basic role of Winner-take-all is rather simple: among a group of neurons, the neuron with maximum activity level remains active and the rest is deactivated [START_REF] Maass | On the computational power of winner-take-all[END_REF]. This may be a good model for STM (Short-Term Memory) where in a group of cells that receives inputs, the network selects the neurons with maximum activity level and maintains that pattern [START_REF] Ermrntrout | Complex dynamics in winner-take-all neural nets with slow inhibition[END_REF] and σ is a threshold similar to the threshold in [START_REF] Mcculloch | A logical calculus of the ideas immanent in nervous activity[END_REF]. σ is set either for the fanals of a particular cluster or for all fanals in the network.

In addition to the McCulloch-Pitts model in which the neuron fires when its activity level exceeds a threshold, this model also includes the maximum activity level (in a cluster or in the entire network).

The Algorithm

The network is a multipartite recurrent graph that is comparable to the well known where the network does not converge). A steady state is where all the activated fanals remain active and all the deactivated fanals remain deactivated when the algorithm passes from one iteration step to the next.

The graph cycles in linear code graphs may increase the number of iterations for which decoder converges whereas the cycles are an essential feature of the proposed network that provides robustness. Therefore, they are avoided in linear codes whereas in the proposed network having more cycles is desirable.

In the proposed network, the retrieval process is:

≤ i ≤ χ, v (n ij ) ← χ i ′ =1 i ′ =i max 1≤j ′ ≤ℓ w (i ′ j ′ )(ij) v (n i ′ j ′ )) + γv (n ij ) (2.15)
where γ is a memory effect that is taken γ = 1 throughout this report. In words it can be expressed that the activity level of the fanal j in cluster i, v (n ij ), increments by one unit if there is one or more active fanals in cluster with index i ′ . In the retrieval procedure given in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF], the sum

ℓ j ′ =1 in v (n ij ) ← χ i ′ =1 i ′ =i ℓ j ′ =1 w (i ′ j ′ )(ij) v (n i ′ j ′ ) + γv (n ij ) (2.16)
takes all the active fanals in a cluster into account. This could be interpreted as there are more than one active fanal in each cluster. The network is expected to converge to a single clique (with only one active fanal in a cluster) after being fed with an input stimulus. This can be directly deduced from the storage procedure (see section 2.3). Therefore, the mentioned summation contradicts the principles of the network. To resolve this issue, that summation is replaced by the max(.)

function in (2.15). It returns 1 if there is one or more fanals in cluster i ′ that are connected to fanal n ij [START_REF] Gripon | Nearly-optimal associative memories based on distributed constant weight codes[END_REF].

The defect of having a fanal n ij in (2.16) that receives more than one signal from fanals of cluster i ′ may have other solutions. Another proposed solution is the normalization of the emitted signals from cluster i ′ . Thus, instead of sending a single signal to fanal n ij (in (2.15)), the active fanals send a weaker signal each equal to

µ = 1 ℓ j ′ =1 w (i ′ j ′ )(ij) v (n i ′ j ′ ) from i ′ th cluster. The activity level of fanal n ij is then computed as v (n ij ) ← χ i ′ =1 ℓ j ′ =1 w (i ′ j ′ )(ij) v (n i ′ j ′ ) µ + γv (n ij ).
(2.17)

In Fig. 2.8, a situation is illustrated where there are three active fanals in a cluster that each sends a one-third signal. Normalizing the emitted signals in (2.17) turns

1 3 1 3 1 3
Figure 2.8: A situation is demonstrated where three active fanals in a cluster send signals to a fanal in a different cluster. Since for a clique there is only one active fanal in a cluster the signal strength of each active fanal is normalized to get a total signal strength equal to unity.

out to be an improper solution with an error rate performance that is worse than (2.15). Although (2.17) normalizes the receiving signals from several fanals in a cluster but it may not force the principle of the network (which is a clique may only have maximum one active fanal in a cluster). The activity level of fanal n ij depends on other activated fanals in cluster i ′ that may have connections belonging to other stored messages.

After the fanals' activity levels are computed in step (a), next step (b) is

Winner-take-all rule. The very first step before applying Winner-take-all is obtaining the maximum activity level in the network for the current iteration step. The

PERFORMANCE

53 maximum activity level in cluster i, v max,i is given by ∀i,

1 ≤ i ≤ χ : v max,i ← max 1≤j≤ℓ (v (n ij ))
and finally the absolute maximum activity level in the network is given by

v max ← max 1≤i≤χ (v max,i ) .
Next, Winner-take-all sets the fanals having the maximum activity level, v max , and above the threshold σ i to 1. This is formulated as

∀iandj, 1 ≤ i ≤ χ, 1 ≤ j ≤ ℓ : v (n ij ) =    1 ifv (n ij ) = v max andv max ≥ σ i , 0 otherwise (2.18)
where σ i is the threshold of a cluster with index i in the network.

Performance

The storage and retrieval procedures of the proposed neural network memory were explained previously. The network performance in different scenarios is addressed in this section where the retrieval success rate (or correspondingly the retrieval error rate) is the main subject.

The network performs a successful recovery when it converges to a unique clique (corresponding to the stored message) after being fed by a stimulus. The recovery of stored messages in the network may be erroneous. The errors are categorized into two kinds: (Type I) The networks converges to a unique clique.

This clique either corresponds to another stored message (with higher order) or it may be constructed from other stored messages' connections (it does not represent any of the stored messages). (Type II) The network dynamics finalizes towards a steady state where there are more than one active fanal in a cluster. Having more than a single active fanal in a cluster is so-called ambiguity. To clarify this point, CHAPTER 2. SPARSE NEURAL NETWORK MEMORIES an ambiguous situation example where the network is not certain about the right clique is illustrated in Fig. 2.9. Therein, it is assumed that a message of order four (with four sub-messages) is stored. The network is fed with three known sub-messages that activate their corresponding fanals marked with black and they are connected with solid lines. The network dynamics activate two other fanals in a cluster ( the cause of ambiguous state in the network) that are connected to the known fanals with dashed lines. In this case, the network can not answer which clique is the correct one. It is also possible that the network does not converge. A special case study is given later in this chapter where the network never converges (see section 2.5.1).

In such situations, the network may stop after a pre-defined maximum number of iterations.

PERFORMANCE

55

Assume the retrieval procedure recovers m and the stored message is m ∈ M.

The error is defined as random variable [CT06]

E =    1 if m = m, 0 if m = m.
(2.19)

The probability P e = Pr[E = 1] = Pr[m = m] is the retrieval error probability.

Note that the condition, m = m, addresses both Type I and Type II errors in the network. In case a Type II error takes place, the network returns a message/sign (e.g. an empty message) to indicate that it could not give a response. Indeed, where there is an ambiguity in a cluster the network is doubtful about the right clique representing the stored message.

Associative Memory

The most important function of the proposed network is Associative Memory. The network provides a neural memory whose contents can be accessed by known parts of the stored messages. Assume a set of sparse messages of size χ each having c significant sub-messages is stored in the network. A message in the stored set is retrieved by knowing a part of it. This is so-called partial message in which a few of the significant sub-messages are missing.

Recovering messages from their corresponding partial messages are considered for two distinct cases: (a) The partial messages consists only of a few known sub-messages and their corresponding positions in the message. This is so-called blind recovery since the positions of missing sub-messages in the support of the original message are not known. (b) The partial message consists of a few known sub-messages and the support of the original message is known. Therefore, the network is a priori aware of the clusters in which the sub-messages are missing. This is so-called guided recovery.

The recovery of the two mentioned types is explained and their corresponding retrieval probabilities are given in the following.

Guided Recovery

In guided recovery, the network is fed with a few known sub-messages (but not all) and the support of a stored message. This facilitates the recovery procedure due to the fact that the network dynamics are a priori aware of the cluster indices in which the fanals are missing. This simplifies down the retrieval situation to the network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] with the same retrieval error rate for the first iteration.

Therefore, the retrieval error probability is given by

P e = 1 -(1 -d c-ce ) (ℓ-1)ce (2.20)
where c e is the number of missing sub-messages.

Blind Recovery

The network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] stores messages of order c that are not sparse therefore all clusters are exploited for the storage. In the proposed network, the messages are sparse and the network exploits this: it only stores the significant sub-messages of a message in a clique. Afterwards, when the network recovers a message from its partial message, it has to spot two different types of information for each missing sub-message. These are the cluster index and the fanal that represent the missing sub-message. This is a more complicated retrieval in comparison with the retrieval procedure of the classical network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF].

The network that is stimulated with a partial message for which the support Assume a fanal that does not participate in the construction of the sought clique. The probability that this fanal is not connected to all known fanals is now computed. This is the probability that the fanal is connected to any number of known fanals in {0, 1, 2, ... , (cc e -1)} but not all cc e fanals. It is computed through binomial distribution as

P s = 1 - c-ce -1 i=1 c -c e i d i (1 -d) (c-ce -i) = 1 -d (c-ce )
where d is the success probability. Now this is extended to the entire network.

The probability of not having an irrelevant fanal in the entire network (comprising the partially known message subject to recovery) is computed through binomial distribution

P r = ce (ℓ-1) i=1 c e (ℓ -1) i P i s (1 -P s ) (ce (ℓ-1)-i) + ℓ(χ-c) i=1 ℓ(χ -c) i P i s (1 -P s ) (ℓ(χ-c)-i) = P [ce (ℓ-1)+ℓ(χ-c)] s = (1 -d (c-ce ) ) [ce (ℓ-1)+ℓ(χ-c)]
where the first sum computes the probability of not having any irrelevant fanal from the clusters in which the missing sub-messages activate their corresponding fanals. There are c e (ℓ -1) irrelevant fanals in those clusters. The second sum is the probability of not having any irrelevant fanals from other clusters that do not participate in the message clique. There are ℓ(χc) such fanals. The probability CHAPTER 2. SPARSE NEURAL NETWORK MEMORIES of error for the first iteration is then:

P e = 1 -P r = 1 -(1 -d (c-ce ) ) [ce (ℓ-1)+ℓ(χ-c)] .
(2.21)

In this recovery procedure, the network retrieves the messages with only one iteration since more iterations can not improve the performance. To explain the Figure 2.10: A situation in the network that cause fanal activity oscillation. This is when the fanals indicated with star markers are activated in odd iteration steps and deactivated in even iteration steps.

reason that results in a single iteration retrieval for blind recovery, an example is given in Fig. 2.10. The network is stimulated with a partial message that activates Fanal (9, 13) is a false fanal that is connected to all three known fanals (1, 4), (3, 7)

and (6, 5). At the end of the first iteration step, the activity levels of fanals are v (n 1,4 ) = v (n 3,7 ) = v (n 6,5 ) = v (n 7,3 ) = v (n 9,13 ) = 3. Therefore, all these fanals remain activated and passed to the second iteration step. At the end of the second iteration step the activity levels are v (n 1,4 ) = v (n 3,7 ) = v (n 6,5 ) = 5

and v (n 7,3 ) = v (n 9,13 ) = 4. Thus, fanals v (n 7,3 ) and v (n 9,13 ) are deactivated.

This resets the network to the initial state before the first iteration. In Fig. 2.11, Type III error rate is depicted along with the total error rate for a network that has χ = 100 clusters and ℓ = 128 fanals in each cluster7 . It can be observed that more than 30% of the errors after the second iteration are Type III. It is also observed through experiments that in blind recovery several iterations do not improve the performance.

In Fig. 2.12 the network performance is illustrated through simulation where it is used as an associative memory. The network has χ = 100 and ℓ = 64 fanals in each cluster. The messages have c = 12 significant sub-messages and they are recovered from partial messages with c e = 3 unknown sub-messages. The solid line is the theoretical blind retrieval error given by (2.21) and the dark square markers indicate the corresponding simulation results for a single iteration retrieval. The dashed line is the theoretical guided retrieval error rate in (2.20) and dark rhombus markers are the corresponding single iteration simulation results. The simulation results of a four iteration recovery is shown with dark triangle that demonstrates a significant improvement with respect to the single iteration retrieval.

Variable Order Messages

Assume the network stores a set of variable order i.i.d. messages. A message has an order c that is uniformly distributed between c min and c max , c min ≤ c ≤ c max . The blind recovery retrieval error rate is then given by

P e = 1 - 1 c max -c min + 1 cmax c=c min (1 -d (1-ǫ)c ) [(ℓ-1)ǫc+(χ-c)ℓ]
(2.22)

where ǫ = c e /c is the ratio of the number of unknown sub-messages to the message order. In Fig. 2.13, the blind retrieval error rate for a network with χ = 100 clusters and ℓ = 64 fanals in each cluster is shown. There are two distinct simulations for 6 ≤ c ≤ 18 and 12 ≤ c ≤ 24. It is observed that the simulation results depicted with dark markers lie on the theoretical curves given by (2.22) (the solid and dashed lines).

Blurred Messages

The proposed network exploits cliques that are redundant structures to store messages, therefore, the error correction of distorted messages such as noisy or permuted messages is possible.

A message from a stored message set (in the network) in which the submessages are slightly changed due to a sort of disturbance is so-called a blurred message. The sub-messages of a blurred message may not be equal to those that are stored in the original message but they are close (e.g. with respect to Euclidean distance measure). Assume the network has a priori knowledge of the disturbance (e.g. the disturbance is a Gaussian noise with variance 1). To recover the original message, the network activates a few hypothetical fanals (depending on the disturbance) that may be close to the correct ones. Thereafter, the network performs the retrieval procedure that may converge to a unique clique that is associated with the original message.

In order to demonstrate this capability, the problem of recovering permuted messages is considered here. For example "intelligence" is a twelve letter English word that may be received either as "nietllgineec" or "etnleilegcni". If the network is able to recognize "intelligence" from these pairwise permuted versions, it is also able to correct less disturbed ones such as "intleligecne" or "intellgienec". The human brain is reputed for having the capability of recognizing simple permutations in the words [START_REF] Grainger | Does the huamn mnid raed wrods as a wlohe?[END_REF].

Having a priori knowledge that the disturbed sub-messages are close to the original message implies that the network needs to be stimulated by activating the corresponding close fanals. In the given example above, a limited permutation is considered where pairs of letters in a word are randomly permuted. To recover the original message it is required to activate the corresponding fanals of each submessage and its neighbour (left and right) sub-messages. Therefore, in each cluster there are three fanals that are initially activated. The retrieval error probability is the probability that at least one of the permuted fanals (that corresponds to a sub-message) constructs a false clique in the network. This is given by

P e = 1 -(1 -d c-1 ) 2c .
(2.23)

In Fig. 2.14 the network with χ = 100 clusters and ℓ = 64 fanals in each clusters recovers permuted messages after the first and sixth iteration steps. It can be observed from the illustrated simulations and theoretical (2.23) that the given retrieval error probability may be achieved after several iteration steps.

Assume an extreme situation where all fanals are activated to find the stored message. This occurs when the close fanals (to the stored fanals) may not be explicitly determined or all fanals may equi-probably participate in the stored clique. The retrieval error probability is given by

P e = 1 -(1 -d c-1 ) c(c-1) .
(2.24)

Set Implementation

In this situation, the network stores a set of messages (one at a time or the whole set at once) and it can be asked afterwards if a hypothetical message (the message to be verified whether it is stored) is stored.

The query procedure (i.e. algorithm) is the one elaborated in section 2.4.2 exploiting (2.18) and (2.15). The threshold in (2.18) is equal to the number of significant sub-messages, 1 ≤ i ≤ χ, σ = σ i = c. The under test message activates its corresponding fanals. If the message exists as a stored message, the 2.5. PERFORMANCE 65 network converges to the fed message. If the network does not return the fed message, the message has not been stored yet.

As said before, the network always converges if the fed message is already stored in the network. This stems from the retrieval algorithm in which, if all of the fanals of a stored message are activated, there is no other fanals in the network with an activity level higher than the activated fanals. Assume a message of order c and the memory effect γ = 1. The fanals of this message in the network have activity level equal to c whereas any other competing fanal can have maximum score c -1, since it can not receive any signal from its own cluster. The correct message fanals receive c -1 signals from other activated fanals (associated with the message) in addition to the memory effect that results in an activity level equal to c. Therefore, a mistake is not possible if the network is asked to verify a stored message. It can be concluded that one iteration is sufficient and necessary but not more.

Although recovering back a stored message in the network is certain, there are other cases for which the network fails. This is when the network is fed with a message that is not stored but it converges and return the message. This may be mistakenly interpreted as the message was stored. This phenomenon is related to false cliques. These are cliques that are not associated with any of the stored messages but are created from the combination of two or more stored messages' connections. Therefore, by assuming again that the connections in the network are asymptotically i.i.d. and uniformly distributed, the probability of detecting a false clique (associate with a hypothetical message that was never stored) is

P False-Clique = d c(c-1) 2 = 1 -1 - c(c -1) χ(χ -1)ℓ 2 M c(c-1) 2 (2.25)
where c is the message order of the hypothetical message. In Fig. 2.15, the simulation results are illustrated along with the theoretical error probability given by (2.25). In this simulation, the network has χ = 100 clusters with ℓ = 64 fanals CHAPTER 2. SPARSE NEURAL NETWORK MEMORIES in each cluster. The densities from which the network stores more messages than limited by the efficiency-1 diversity (see section 2.3) is indicated with "×" and "+".

These points are computed through (2.9). It can be observed that even though the network is overloaded, the probability of false detection is very low. From this, it can be concluded that the network can be employed for set implementation reliably with efficiencies larger than one: η > 1.

Optimal Network

The network and the message set need to be designed in order to establish an efficient and optimal neural. The optimality can be based on different cost functions.

OPTIMAL NETWORK

67

The network is optimized with respect to two cost functions: the retrieval error rate and the network diversity. In the previous sections the given equations have established the relations among the network message set parameters and these cost functions. The network parameters are cluster space size χ and number of fanals in each cluster ℓ. The parameters of stored the message set are the minimum and maximum message orders (c min and c max ) and number of stored messages M.

These two sets of parameters are related by retrieval error probability, density and diversity equations.

Optimal Constant Message Order

The network with cluster space size χ and ℓ fanals in each cluster stores a set of messages with constant order c. As a design parameter, the optimal message order c is computed to maximise the number of stored messages.

The blind retrieval error probability in (2.21) is rewritten as

P r = (1 -d (c-ce ) ) [χℓ-(ǫ+(1-ǫ)ℓ)c] ≈ (1 -d (1-ǫ)c ) χℓ (2.26)
where ǫ = c e /c. The network density is approximately computed as

d ≈ (1 -P 1 χℓ r ) 1 (1-ǫ)c .
For low density values d ≪ 1 in (2.6), the number of stored messages is approximately given by

M ≈ d χ(χ -1)ℓ 2 c(c -1) .
After taking the derivative of M with respect to c, the approximate optimal message order for a specific error rate P 0 is

c opt ≈ log χℓ P 0 2(1 -ǫ) .
(2.27)

In Fig. 2.16, the number of messages versus the message order c is illustrated. It is observed that the number of stored messages reaches a maximum for a specific c that is given approximately by (2.27). The optimal message order can be used as a rule-of-thumb to design networks that store variable order messages by choosing the average order close to (2.27).

Optimal Density

The optimal density refers to a density for which the network exploits the connections efficiently. This is when the connections bear the maximum amount of information. The connections of the network take binary values and each can be considered as a Bernoulli random variable. Bernoulli random variables bear the maximum amount of information when their success probability is 1 2 . So, a network that exploits efficiently its connections is the one with density d = 0.5. Therefore, the connection matrix in (2.3) does not need to be compressed when it is being transferred or stored on a device.

Optimal Variable Message Order

A network that stores variable order messages is more complicated to optimize although it has more capabilities (storage of variable order messages). To optimize the network two criteria are considered: the density d = 0.5 and the recovery error rate. It is aimed to find c min and c max for which the network has the least (or very low) retrieval error probability while d = 0.5. To achieve this goal, the network density in (2.11) where 1 χ(χ-1) ≪ ℓ 2 is rewritten as

d ≈ 1 -(1 - 1 ℓ 2 ) M k=1 c k (c k -1) χ(χ-1) (2.28)
where M is large and c k (c min ≤ c k ≤ c max ) is the kth message order. The message orders c k are assumed to be uniformly distributed between c min and c max .

The number of messages with order c is M c = M cmax-c min +1 (based on an axiom of probability theory described in [START_REF] Papoulis | Probability, Random Variables and Stochastic Processes[END_REF]p. 11]) that results in

d ≈ 1 -(1 - 1 ℓ 2 ) M k=1 c k (c k -1) χ(χ -1) = 1 -(1 - 1 ℓ 2 ) Mc cmax c=c min c(c -1) χ(χ -1) = 1 -(1 - 1 ℓ 2 ) M E{(c-E{c}) 2 }+E{c} 2 -E{c} χ(χ-1) (2.29)
where c (in bold) is the message order random variable (uniformly distributed).

Mean of random variable c is

E{c} = c max + c min 2
and its variance is

E{(c -E{c}) 2 } = (c max -c min + 1) 2 -1 12 .
In Fig. 2.17, the network is optimized for the maximum connection entropy, that is, for d = 0.5. It can be observed that there may be several combinations of c min and c max for which the network holds d = 0.5 when it stores a certain number of messages. In practice one should choose the best among these choices.

A criterion may be the error rate for which each application requires a particular error rate. For example, image processing applications can tolerate high error rates while telecommunication systems generally need an error rate lower than 10 -4 .

CHAPTER 3. INFORMATION-THEORETIC ANALYSIS OF THE NEURAL NETWORK MEMORY

visual cortex) and then possibly stored with some added redundancy in order to ensure robustness and durability. This flow of neural signals that convey information (which results in learning, moving a muscle, etc.) can be measured [START_REF] Borst | Information theory and neural coding[END_REF],

but the information-theoretic study of the biological neural systems such as the human brain is not really the subject of this thesis. This chapter is focused on artificial neural networks.

The neural memory proposed in chapter 2 will be discussed exploiting the information theory framework, that is, the storage and recovery of messages from their partially known or distorted messages will be studied from source and channel coding aspects. In particular, the last section is dedicated to information-theoretic constraints on the proposed network.

Analysis of the Message Source

The very first step toward the information theoretic analysis of the proposed neural network is the investigation of the message source. Throughout this report, it is assumed that the message source is i.i.d. and uniformly distributed. Such a source has the maximum entropy and therefore is intrinsically compressed. Moreover, this assumption simplifies the study of the network without loss of generality. Once the network is mathematically formalized for the i.i.d and uniformly distributed source of messages, it can be extended to other types of sources (by knowing their probability density function).

In chapter 2, the retrieval error probability of the network was formulated in (2.20) and (2.21) for the first iteration. These error probability equations are upper bounds on the performance of the network, that implies that the network may have a lower error rate with more than one retrieval iteration step. In this section, a lower bound on the retrieval error probability is computed to demonstrate that even if the network stores two messages, the error probability may not be zero.

ANALYSIS OF THE MESSAGE SOURCE

73

The lower bound is computed based on the typical sequences fundamentals [CT06,

Chapter 3].

Assume the network tries to retrieve the stored messages from their corresponding partial messages in either guided recovery or blind recovery (section 2.5.1) schemes. The network stores two messages of the same order c. The probability of these two messages having r distinct sub-messages is equal to

c r (1 -1/ℓ) r (1/ℓ) (c-r )
where 1 < r < c. Although the two messages are distinct and can be retrieved, there is a situation in which none of them can be recovered. Assume the network retrieves one of the messages when being fed with a partial message. The partial message has c e missing sub-messages that are chosen uniformly random among c sub-messages of either of the two messages. In case the r non-identical submessages are missing, an ambiguity situation occurs (see section 2.5) that even a genie decoder is not able to resolve. The probability of having the r non-identical sub-messages (1 < r < c) missing in a partial message is equal to

ǫ r (1 -ǫ) (c-r )
where ǫ = c e /c. The probability P L that the network is not able to retrieve a stored message from its corresponding partial message is then lower bounded as

c r (1 -1/ℓ) r (1/ℓ) (c-r ) ǫ r (1 -ǫ) (c-r ) < P L .
This trivial lower bound (regardless of the number of iterations) is imposed by the message source and the network architecture.

For example consider two messages that are drawn from A = {1, 2, ... , 128}

and stored in a network with eight clusters. This operation can be represented as an element-wise multiplication of two vectors

m 1 and O = [-, 0, -, 1, -, 1, 1, -]
where 0 represents the missing sub-message. The partial message is obtained as

m par = m 1 ⊙ O = [-, 0, -, 14, -, 78, 35, -].
Message m 1 can not be retrieved from this partial message, because the same operation on m 2 gives the same result.

Channel Coding

Channel coding is the technique of adding smart redundancy to information in order to preserve the original information where it is exposed to distortions. A common application of channel coding is data protection in communication systems where a transmitter sends information to a receiver over a noisy channel. Transmission over a noisy communication channel may result in the erroneous reception of information at the receiver. Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF] and Hamming [START_REF] Hamming | A mathematical theory of communication[END_REF] separately addressed this problem by proposing error correction codes to protect the transmitted information. Shannon showed that there is a code through which a system can rich a maximum communication rate known as channel capacity [START_REF] Shannon | A mathematical theory of communication[END_REF]. Since then, researchers looked for such codes to achieve channel capacity. Turbo code [START_REF] Berrou | Near optimum error correcting coding and decoding: turbo-codes[END_REF] and LDPC code [START_REF] Gallager | Low-density parity-check codes[END_REF] are two examples of linear codes getting close to Shannon limits. Although the formal definition of a code in [START_REF] Richardson | Modern Coding Theory[END_REF][START_REF] Lin | Error Control Coding[END_REF] does not impose any constraint on the decoding and encoding procedures, these are of great

CHANNEL CODING

75 importance in practice. Encoding is the mapping of an input information to its corresponding codeword and decoding is retrieving the original input information from the distorted codeword. Since in practice an efficient code is enormously large (M is large), encoding and decoding algorithms are the main concern in coding theory (along with error correction capabilities of codes). There are not many successful coding schemes that comply both encoding/decoding and error correction capability requirements. Turbo and LDPC codes may be the master pieces of this never ending quest until now. These are linear codes that rely on parity check matrices. They are also known as generator matrices which are used to generate codewords. Properties of a code including error detection and correction capabilities, depend on codewords and computing the generator matrix from the codewords is formidable and non-trivial. Consequently finding such matrices that generate desirable codes 1 is difficult.

The classical network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] and the proposed network in this report attack the channel coding differently. The neural network provides a memory to store the codewords and a practical decoding algorithm. Unlike linear codes, the codewords are not extracted from a generator matrix. The network is capable of storing an arbitrary set of codewords that may or may not be linearly dependent with respect to each other, which is another degree of freedom. Therefore, the designer is able to choose each codeword (theoretically) carefully depending on system requirements.

The code rate of the system depends on the number of messages (i.e. codewords) which the network is able to store and recover. It is

R = log ℓ (M) c (3.1)
where M is the cardinality of the code (it is also defined in chapter 2 as the number of stored messages), ℓ is the number of fanals in each network cluster and c is the 1 Desirable codes may be described by various metrics such as minimum Hamming distance [START_REF] Lin | Error Control Coding[END_REF][START_REF] Hamming | A mathematical theory of communication[END_REF].

CHAPTER 3. INFORMATION-THEORETIC ANALYSIS OF THE NEURAL NETWORK MEMORY code block-length (i.e. message order).

There are two main differences between the network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] and the proposed network when they are used for channel coding applications. The number of codewords of a linear code is remarkably large in comparison with the diversity of the neural network in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF]. The proposed network (in this report) has a larger diversity (see section 2.3) than the classical one, which helps the network diversity get closer to the cardinality of linear codes. The second advantage of the proposed network is the storage of codewords with different lengths (i.e. variable message orders). This makes the system able to exploit non-block codes (where the codewords have different lengths). The system may also implement a multirate coding system with a variable coding rate depending on the communication channel quality.

Source-Channel Coding

In chapter 2, it was briefly mentioned that the network is capable of both compression and protection of the stored messages. This is known as source-channel coding where input information is compressed to remove its redundancy and then a smart redundancy is added to protect the compressed information against distortions. Consider the set-implementation application of the network in which the message support set and correspondingly the active clusters are a priori known.

It was observed in set-implementation (see section 2.5.3) that the false detection rate is very low even for network efficiency η > 1. A network efficiency larger than unity implies that the network stores more information bits than its maximum available bits Q (equation (2.4) in section 2.3). The compression and error protection features of the network allow a low false detection rate when η > 1. This is a kind of joint source-channel coding similar to the classical method in [START_REF] Lin | Error Control Coding[END_REF][START_REF] Cover | Elements of Information Theory[END_REF] that is elaborated in the following.

SOURCE-CHANNEL CODING

77

A message of order c is mapped to a clique with c 2 = c(c -1)/2 binary connections. The message contains c log 2 ℓ bits. Therefore, to compress a single message at the storage, inequality c -1 2 < log 2 ℓ must be held. For example, previously in chapter 2 a simulation result was given for a network with ℓ = 64 that stores messages of order c = 12. By substituting the network parameters in the inequality, it is found that the network satisfies the inequality, (12 -1)/2 < log 2 64. The network compresses further the messages through sharing connections. For example consider messages that share 3 2 = 3 connections in their corresponding cliques. The total number of connections to store the two messages is equal to 2 × 4 2 -3 2 = 9 instead of 12 (when they are stored separately as single messages). The above example simply shows that a set of stored messages with some equal sub-messages requires a fewer number of connections to be represented in the network. This feature, when the network stores a large number of i.i.d. and uniformly distributed messages, results in compression.

m 1 = [-,
A clique has a redundant structure, i.e., the c active fanals belonging to a message are linked through c(c-1) 2 connections whereas ⌊ c+1 2 ⌋ may be enough to connect them together 2 (the minimal number of required connections to represent a message). Therefore, due to such redundancy feature, a clique in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF] is considered as a clique code (similar to a codeword) that protects the message.

The classical codes introduced by Hamming are characterized by a well known

2 ⌊q⌋ is the largest integer not greater than q. The minimum distance is defined as the number of different edges between these two cliques [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF], which is

d min = 2(c -1) (3.2)
when the cliques have order c. In [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF], the authors defined the coding rate R as the ratio of minimum number of edges to associate a set of nodes and the number of edges in a clique which is R = 1 c-1 . The coding rate is an important parameter in coding theory. It quantifies the increased redundancy in order to provide error correction and detection capability. It is therefore desired that the code has a coding rate close to unity, i.e., having less redundancy as possible. This is further used to derive a parameter namely the merit factor F = Rd min . In the proposed network and in the one in [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF], F is equal to 2, indicating that clique codes are good codes [START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF].

Communication Channel Model

A memory is expected to recover exactly what has been stored in it. This however does not happen in real-world applications. Memory contents change throughout time due to physical changes in their semiconductor substructure, electromagnetic interference, solar activities, etc. The proposed neural network memory like other types of memories is not error-free. Therefore, a part of stored information may not be recovered (see section 3.1). Erroneous recovery imposes limits on the neural network quality which is highly dependent on the number of stored messages M and

COMMUNICATION CHANNEL MODEL

79

the number of unknown sub-messages at the input. From the error probabilities computed in chapter 2, the maximum number of stored messages can be estimated when the error rate is below a certain limit. Although this is a very useful rule-ofthumb, it may not be a precise criterion, because the error rate limit may change from one to another application. Information-theoretic analysis is an approach that could give rigorous limits on the proposed network rather than vague limits based on intuition. It has been previously considered in [START_REF] Schwenker | Iterative retrieval of sparsely coded associative memory patterns[END_REF][START_REF] Abu-Mostafa | Information theory, complexity and neural networks[END_REF] for neural network memories. In the following, information theory is exploited to compute a set of constraints on the proposed network when it is used as an auto-associative memory.

Unreliability in memories can be modeled as a communication channel for which there are known information-theoretic analysis. A communication channel is a probabilistic model to compute information loss in systems in which information is distorted randomly (that is, when the distortions can not be modeled as the result of a deterministic alteration of input and output information). In Fig. 3 gives after the recovery. In this case, the network would loose information in the process of decoding. The differential information rate is defined as

I diff = I (m; m) -I (m; m) = H(m| m) -H(m| m) (3.3)
where H(.|.) is the conditional entropy between two random vectors/variables and the network is informative if I diff > 0. The computation of I diff requires the computation of I (m; m) and I (m; m). They are derived in the following sections.

Puncturing Block Channel Model

The proposed network is an auto-associative memory which recovers a message from its corresponding partial version. It was mentioned earlier that the missing sub-messages (in a partial message) are distributed uniformly random among significant sub-messages. To be precise, partial message m is message m with order c in which c e sub-messages are missing. A sub-message in m may be unknown in m with probability ǫ = c e /c (ǫ was introduced first in section 2.5.1). The generation of partial messages is assumed to be performed by a function, namely puncturing block. This block is modeled as a Discrete Memoryless Erasure Channel (DMEC) [START_REF] Cover | Elements of Information Theory[END_REF][START_REF] Proakis | Digital Communications[END_REF] in which a sub-message is either passed through the channel (unchanged) with probability 1ǫ or it is mapped to null (here it is shown with 0) with probability ǫ. This channel model is depicted in Fig. 3.3. The amount of information at the DMEC input is equal to the sub-message's entropy H(x) where

x is the sub-message random variable. Because x is assumed i.i.d. and uniformly distributed over alphabet A with cardinality ℓ, H(x) = log 2 ℓ [START_REF] Cover | Elements of Information Theory[END_REF]. z is a random variable which takes values in A ∪ {0}. It represents the sub-messages that are passed through the puncturing block. The remained amount of information (in a sub-message) after the puncturing operation is computed through mutual information rate

I (x; z) = H(x) -H(x|z) = H(x) - z P(z)H(x|z = z) = H(x) -ǫH(x|z = 0) = (1 -ǫ)H(x). (3.4)
The mutual information rate in (3.4) has a simple relation with source entropy H(x): it reaches its maximum when there is no missing sub-messages, i.e., ǫ = 0 and it reaches its minimum when all sub-messages are missing (ǫ = 1).

The random vector m can be decomposed into a c-tuple vector of c i.i.d. ran-

CHAPTER 3. INFORMATION-THEORETIC ANALYSIS OF THE NEURAL NETWORK MEMORY

dom variable x (sub-message random variable) and a support vector which holds the indices of the c significant values in m. Therefore, the entropy of the message random vector is equal to

H(m) = log 2 χ c + cH(x) = log 2 χ c + c log 2 ℓ
bits, where the first term in the sum is the support vector entropy and the second is the significant sub-messages' entropy. The separation of the support vector and sub-messages entropies is of great importance, because the network may recover in two different modes: guided recovery and blind recovery. In guided recovery, the network is fed with the complete support vector information and in blind recovery, it is fed only with the support vector of the known sub-messages. The mutual information rate for guided recovery is computed as

I G (m; m) = log 2 χ c + c i=1 I (x; z) = log 2 χ c + c(1 -ǫ) log 2 ℓ.
(3.5)

In (3.5), the sum over I (x; z) is the implication of the previous assumption: the mutual information rate of c i.i.d. random variables in a vector is the sum of each random variable's mutual information rate [START_REF] Cover | Elements of Information Theory[END_REF].

In blind recovery, the support vector gives only the indices of c e = (1ǫ)c known sub-messages. Therefore, the support vector requires log 2 χ

(1-ǫ)c bits to be represented. The mutual information rate for blind recovery is computed as

I B (m; m) = log 2 χ (1 -ǫ)c + c i=1 I (x; z) = log 2 χ (1 -ǫ)c + c(1 -ǫ) log 2 ℓ.

Neural Network Memory Channel Model

Set of stored messages M passes through the network (as a black box) and is mapped to a set of retrieved messages. Although the internal storage and retrieval procedures of the messages are known, the underlying mapping between the set of stored messages and retrieved messages may not be easy to predict. This is worsen when considering more than one iteration step at the retrieval.

The recovery error was defined in section 2.5. If the network fails to recover even one sub-message in a message, an error occurs (although there may be correctly recovered sub-messages). By definition, an erroneous recovery bear no information about the stored message and its sub-messages, i.e., I (m; m|m = m) = 0. This is to guarantee the network functionality as a memory which is aimed to retrieve what has been stored. In Fig. 3.4, the network channel model that maps m to m is shown. The network mutual information rate is equal to

I (m; m) = log 2 χ c + (1 -P e )H(m) = log 2 χ c + (1 -P e )cH(x) = log 2 χ c + (1 -P e )c log 2 ℓ (3.7)
where P e is the network error probability. P e was given in section 2.5.1 for the single iteration blind and guided recoveries.

Recovery Constraints: Differential Information Rate

The first recovery constraint is guided recovery computed by simply substituting (3.7) and (3.5) into (3.3). Inequality P e < ǫ (3.8)

COMMUNICATION CHANNEL MODEL

85

holds when the network is informative, i.e., I diff > 0. From substituting (3.7) and

(3.6) into (3.3), the blind recovery constraint is computed,

P e < 1 c log 2 ℓ log 2 χ c χ (1-ǫ)c + ǫ (3.9)
when the network is informative. In Fig. 3.5, the differential information rate (as error probability P e are depicted. The network remains in the informative region, i.e., I diff > 0 if its recovery error rate is below the upper bounds. It is observed that the error probability upper bound for blind recovery grows faster and it reaches the unity where ǫ = 0.63. This suggests that the network may not be in the informative region for ǫ ≥ 0.63. Proof. Fano's inequality is written separately for H(m| m) and H(m| m).

Recovery Constraints: Fano's Inequality

H(P e ) + P e H(m) ≥ H(m| m).

(3.12)

H(ǫ) + ǫH(m) ≥ H(m| m). (3.13)
The information rate of the puncturing block is

I (m; m) = H(m)

Discussion

Two sets of upper bounds on P e for blind and guided recoveries were computed in sections 3.4.3 and 3.4.4. The first upper bounds in section 3.4.3 were computed by condition I diff > 0. In section 3.4.4, in addition to the condition on I diff , Fano's inequality was also used. Moreover, for the computation of the bound in Theorem 1 the network was not modeled as a DMEC. Indeed, the network may be considered to be any procedure which recovers m from m.

Fano's inequality is often exploited to obtain lower bounds on error probability.

Theorem 1 computes the lowest value of P e for which I diff < 0. This implies that if the network error probability is equal to P ′ e and P ′ e < P e , then I diff > 0. Thus the given bound in Theorem 1 depends on not only I diff but also Fano's inequality. This signal is not intrinsically sparse but its Fourier transform coefficients' vector is sparse. The nonzero coefficients are spikes on the frequency spots in which the sinusoids oscillate. Therefore, the coefficients form a sparse vector in which the informative parts are the nonzero elements.

Definition. A signal is k-sparse if its representation in a basis has only k nonzero coefficients [START_REF] Baraniuk | Compressive sampling[END_REF]. A vector is k-sparse if it has only k nonzero elements1 .

CHAPTER 4. INFORMATION-THEORETIC CONSTRAINTS ON SPARSE PATTERN RECOVERY

Although sparse signals and vectors are desirable, they are rare in practice.

There may be a basis in which a signal is sparse along with very small nonzero residuals [START_REF] Stojnic | Explicit thresholds for approximately sparse compressed sensing via ℓ 1 -optimization[END_REF]. This is the dominant situation in real-world applications. In order to have a purely sparse (without tiny residual coefficients), the signal must be noise-free (as a counterexample) and this is not usually the case. Besides, practical signals are naturally random and to find a basis that gives strictly sparse coefficients may not be feasible.

Definition. A vector is strictly sparse when there are only a few nonzero elements.

A vector is approximately sparse when there are a few significantly large coefficients and the rest is small but not necessarily zero [START_REF] Baron | Bayesian compressive sensing via belief propagation[END_REF][START_REF] Stojnic | Explicit thresholds for approximately sparse compressed sensing via ℓ 1 -optimization[END_REF].

Sparseness or parsimony is an a priori knowledge about a signal. It may be exploited to improve the performance of information processing systems. In this report, the situation in which these signals have to be sampled and stored is considered. There are other applications such as blind deconvolution [START_REF] Herrmann | Fighting the curse of dimensionality: Compressive sensing in exploration seismology[END_REF][START_REF] Zhao | On compressed blind de-convolution of filtered sparse processes[END_REF] that are not discussed here. stored. This scheme has several drawbacks. It requires to sample at Nyquist rate or higher that implies that the system acquires and stores enormous amount of redundant information. This imposes a data processing burden on the encoder whereas the decoding is less energy and computationally demanding. It may also lead to some practical limitations, especially in the hand-held devices and sensor networks where the devices are battery driven.

Compressed-sensing is an emerging field for compression and signal acquisition.

It is the joint sampling and compression of sparse signals that is aimed to reduce the complexity of encoders. In this scheme, sampling and compression are not separate procedures (i.e. serially implemented) but they are performed simultaneously.

The compressed-sensing systems avoid acquisition and processing of redundant information: the sampling rate is proportional to the underlying information content (sparsity level) rather than the bandwidth of the underlying signal [START_REF] Donoho | Message-passing algorithms for compressed sensing[END_REF][START_REF] Taheri | Segmented compressed sampling for analog-to-information conversion: Method and performance analysis[END_REF].

For example in [START_REF] Taheri | Segmented compressed sampling for analog-to-information conversion: Method and performance analysis[END_REF], an under-Nyquist Analog-to-Information Conversion (AIC) scheme is proposed. CS can significantly reduce processing time and power consumption in the encoder (i.e. acquisition system). Moreover, there are situations in which acquiring sampled data is too expensive or practically infeasible. Such situations can be seen in physics experiments when the sensors are too costly or when a quantity is measured in a large spacial volume with few sensors. Although compressed-sensing is an efficient scheme at the sensory level, i.e., signal acquisition, it requires a sophisticated recovery procedure. A compressed-sensing setup is formulated as

Y = XBα = X β (4.1)
where α p×1 is the sparse signal, β p×1 is the sparse vector, B p×p is a basis and X n×p is the sampling matrix. Y n×1 is the sparse signal projection in a lower dimension hyper-space (n < p). It is assumed that β has at maximum k-nonzero elements (or significant elements if β is approximately sparse) and k < p. The system of linear equations in (4.1) is generally so-called compressed-sensing when k/p ≪ 1.

In this report, the system is named compressed-sensing regardless of k/p value. PATTERN RECOVERY

The operations of a compressed-sensing system is packed into an underdetermined set of linear equations where the high dimensional sparse vector is mapped (compressed) into a lower dimensional vector. The compression is a simple mapping whereas the recovery (decompression) is a search for the corresponding vector (with higher dimension). In general such a system of equations has infinite number of solutions. It was first observed in reflection seismology that such a system may have a unique answer. In reflection seismology, a system transmits a series of sparse pulses after which it estimates the transfer function of the traversed path.

It was known that if the pulses are sparse, there may be a unique solution (the transfer function) to the problem [START_REF] Saligrama | Compressed sensing of autoregressive processes[END_REF][START_REF] Zhao | On compressed blind de-convolution of filtered sparse processes[END_REF]. It was later shown (rigorously proved) in [START_REF] Donoho | Compressed sensing[END_REF][START_REF] Candès | Compressive sampling[END_REF][START_REF] Candès | An introduction to compressive sampling[END_REF][START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF]] that an underdetermined system of linear equations has a unique solution under certain conditions. These are algebraic conditions on the sparsity level and the sampling matrix (coefficients' matrix). There are two very well known conditions (among others) derived independently by Candès and Donoho. A sufficient condition on the sampling matrix that is so-called Restricted Isometric Property (RIP) given by Candès [START_REF] Candès | Compressive sampling[END_REF]. A sufficient and necessary condition on the sampling matrix that is so-called Null Space Property (NSP) given by Donoho [START_REF] Donoho | Compressed sensing[END_REF].

Recovery

For sparse enough vectors in underdetermined linear system of equations there is an exact solution [START_REF] Candès | Compressive sampling[END_REF][START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF][START_REF] Donoho | Compressed sensing[END_REF][START_REF] Baraniuk | Compressive sampling[END_REF]. This is an optimization problem that finds the sparsest solution [START_REF] Candès | Compressive sampling[END_REF][START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF].

(P 1 ) minimize α ℓ 1 subject to XB α = Y
is equal to the solution of (P 0 ). Unlike (P 0 ), this optimization problem can be solved by a polynomial time algorithm that is so called ℓ 1 -norm minimization [START_REF] Candès | An introduction to compressive sampling[END_REF]. The importance of this is that Candès and Donoho rigorously showed that if the solution is sparse, there is a unique solution for the underdetermined system and this is obtained in polynomial time where NSP and/or RIP are/is satisfied.

RIP is a sufficient condition whereas NSP is a necessary and sufficient condition which implies that a system satisfying RIP also satisfies NSP [START_REF] Donoho | Compressed sensing[END_REF].

Restricted Isometry Property (RIP)

A sufficient condition for a stable recovery is that the matrix X preserves the length of any k-sparse vector being projected. This implies that the projected sparse vectors are not distorted by projection, therefore, the exact recovery is feasible. On the other hand, this condition is not necessary for the recovery of the signal and there might be other random projections (e.g. sampling matrices with smaller n) that lead to successful recovery.

Definition 6 (see [START_REF] Candès | Compressive sampling[END_REF][START_REF] Candès | An introduction to compressive sampling[END_REF]). A matrix X ∈ R n×p satisfies the RIP of order k ∈ N and isometry constant δ k ∈ (0, 1) if

(1 -δ k ) β 2 ℓ 2 ≤ X τ β 2 ℓ 2 ≤ (1 + δ k ) β 2 ℓ 2 ∀β ∈ R |τ | (4.2)
where τ ⊂ {i ∈ N|i < n} and |τ | ≤ k. X τ is a submatrix of X with column indices from τ .

RIP expresses that every set of columns with cardinality less than k approximately behaves like an orthogonal vector space [START_REF] Candès | Error correction via linear programming[END_REF]. All matrices X t τ X τ This is bearing the pseudo-orthogonal vector space concept. RIP searches grouped vectors as vector spaces for an approximate orthogonality where X τ is a k × |τ | sub-matrix that holds (4.2) for any k-sparse vector in R |τ | .

Theorem 2 (see [START_REF] Candès | Compressive sampling[END_REF][START_REF] Candès | Decoding by linear programming[END_REF]). Assume β is k-sparse and suppose that δ 2k + δ 3k < 1 or, better, δ 2k + δ k,2k < 1. Then the solution β to (P 1 ) is exact, i.e., β = β.

Null-Space Property (NSP)

The Null-Space Property (NSP) is given by Donoho in [START_REF] Donoho | Compressed sensing[END_REF]. This is a necessary and sufficient condition which guarantees that none of the sparse vectors with sparsity level k lies in the null-space of the sampling matrix.

Theorem 3. (see [START_REF] Donoho | Compressed sensing[END_REF]) A measurement matrix, X n×p is assumed. Further, assume that Y = X β and β has at most k nonzero elements and δ p×1 is a p-

dimensional vector. Let K ⊂ {1, 2, • • • , n} such that |K | = k and let K i denote the i-th element of K . Further, let K ⊂ {1, 2, • • • , n}/K . Then (P 1 ) will produce a solution β that satisfies β -β 1 ≤ 2(C +1) C -1 β K 1 if and only if (∀δ ∈ R p |X δ = 0) and ∀K , k i=1 |δ K i | ≤ n-k i=1 |δ Ki |. (4.3)

Verification of the Algebraic Conditions

The verification of both RIP and NSP for a specific sampling matrix is not a tractable task [dE10,dG11]. To verify any of those conditions, an algorithm should test the sampling matrix with a set of sparse vectors of infinite cardinality. This drawback has attracted the attention of researchers to randomly generated matrices (such as Gaussian matrices) and deterministic matrices [START_REF] Candès | An introduction to compressive sampling[END_REF][START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF][START_REF] Donoho | Compressed sensing[END_REF].

COMPRESSED SENSING AND NEURAL NETWORKS

97

The study of recovery conditions for random matrices is simplified since the probability density function of the generated elements is known. The deterministic matrices are generated (to satisfy the algebraic conditions) by carefully choosing the constructing vectors of the sampling matrix. For example in [START_REF] Li | Deterministic construction of compressed sensing matrices via algebraic curves[END_REF], the deterministic construction of sampling matrices is studied. In [START_REF] Donoho | Compressed sensing[END_REF], it is shown that, if the elements of the sampling matrix is drawn from the outcomes of an i.i.d. Gaussian random source, the matrix satisfies NSP.

Compressed Sensing and Neural Networks

Compressed-sensing provides under-Nyquist sampling [START_REF] Taheri | Segmented compressed sampling for analog-to-information conversion: Method and performance analysis[END_REF] and dimensionality reduction. Neural network memory is concerned with learning mechanisms inspired by the human brain and information compression. The key to find the similarities between the two is the mathematical representation of compressed-sensing systems. It is a linear projection that maps a high dimensional sparse vector to a lower dimensional vector (that may not be sparse).

A single-layer feedforward neural network [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF] is similar to compressedsensing formalization as expressed by (4.1). It is a network of input nodes that are connected to the output nodes through weighted connections (the sampling matrix elements). This is simply expressed by a linear projection that maps the inputs as a vector to an output vector [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. An example is Bidirectional Associative Memory (BAM) that was proposed by Kosko et al. in [START_REF] Kosko | Bidirectional associative memories[END_REF]. It is a single-layer recurrent neural network memory that learns pairs of binary vectors in a matrix.

The vector pairs may not have the same length. The recovery type is cued-recall (see section 1.1) where a vector in a pair is retrieved through another one. BAM decoding consisting the linear projection of the key vector (the known vector in a pair) followed by a thresholding function.

Dimensionality reduction is well studied under the formalism of machine learn-and their corresponding lower dimensional pairs.

Information-Theoretic Conditions

The recovery conditions in section 4.1 were derived for an ideal setup when there is no distortion. In practice, sampling devices and digital computations introduce noise to information. have considered information theory as an alternative solution. Information theory stems from probability theory and the noise is intrinsically random and unpredictable. Therefore, such a probabilistic approach may be suitable to study the noisy systems in addition to the discussion given in section 4.1.3.

A noisy system of linear equations is considered for which it is a priori known that the solution is k-sparse (a vector with k nonzero elements).

Y = X β + W (4.4)
where X ∈ R n×p is a random Gaussian measurement matrix with independently and identically distributed (i.i.d.) elements X ij ∼ N (0, 1). β is the k-sparse vector subject to measurement. W is a Gaussian noise vector W ∼ N (0, I n×n ) where I n×n is the n dimensional identity matrix. The support set of β is defined as In this report, asymptotic sufficient conditions (on exact support recovery) depend on the number of measurements n, the sparse vector dimension p, the sparsity level k and the signal-to-noise ratio

supp(β) {i : β i = 0},
SNR = E{||X β|| 2 2 } E{||W || 2 2 } = ||β|| 2 2 , (4.7)
where the noise variance σ 2 = 1 and the measurement matrix elements are drawn from a Gaussian random source output with unit variance and zero mean. Though the signal-to-noise ratio is an important parameter, the exact support recovery In [START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF], the authors assume that β has a mean and variance stationary source. In [START_REF] Baron | Bayesian compressive sensing via belief propagation[END_REF][START_REF] Shihao | Bayesian compressive sensing[END_REF], the authors model the support of a sparse signal as a vector of random elements, in which an element is an outcome of a random source with probability k/p to be nonzero that implies mean stationarity. In [START_REF] Baron | Universal map estimation in compressed sensing[END_REF][START_REF] Jalali | Minimum complexity pursuit: Stability analysis[END_REF] the authors model the high-dimensional sparse vector β as a realization of an ergodic stationary source. In signal processing, random sources are widely modeled as ergodic wide-sense stationary (EWSS) [START_REF] Hayes | Statistical Digital Signal Processing and Modeling[END_REF][START_REF] Haykin | Adaptive Filter Theory[END_REF]. In this work, the sparse vector β is assumed to be random ergodic wide-sense stationary. Even though this assumption is common and most often inevitable in signal processing, it has not been considered in [Wai09,WWR10,Rad11,ASZ10,AT10,SBB06,JKR11, FRG09] to compute the information-theoretic constraints.

Bounds and Recovery Conditions

In [Wai09, WWR10, ASZ10] and this report, Fano's inequality [START_REF] Cover | Elements of Information Theory[END_REF] was exploited to obtain asymptotic constraints on the exact support recovery depending on (p, k, n, λ). Fano's inequality in asymptotic form given in [START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF][START_REF] Rad | Nearly sharp sufficient conditions on exact sparsity pattern recovery[END_REF] is due to its concavity (see the discussion in [START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF]).

log p -k + m m -1 -log 2 ≤ E X I (θ; Y ), (

Strictly Sparse Signals

The recovery constraints in [Wai09,WWR10,Rad11,ASZ10,AT10,SBB06,JKR11, Theorem 4. Assume a measurement matrix X ∈ R n×p whose elements are drawn from the outcome of an i.i.d. Gaussian random source with zero mean and unit variance, i.e., X i,j ∼ N (0, 1). A sufficient condition for asymptotically reliable recovery of a k-sparse ergodic wide-sense stationary signal β in which the nonzero

elements |β i | ≥ λ is log p -k + m m -1 -1 ≤ L (4.9)
where

L = n 2 log 1 + m p -k + m λ 2 (1 - m p -k + m ) n Γ(n) p -k + m -1 n -1 104 CHAPTER 4. INFORMATION-THEORETIC CONSTRAINTS ON SPARSE PATTERN RECOVERY
in which Γ(.) is Gamma function and m = 1, ... , k.

By lower bounding further the information rate (right-hand side of (4.9)), the following sufficient condition is obtained.

Corollary 1. Assume a measurement matrix X ∈ R n×p whose elements are drawn from the outcome of an i.i.d. Gaussian random source with zero mean and unit variance, i.e., X i,j ∼ N (0, 1). A sufficient condition for asymptotically reliable recovery of a k-sparse ergodic wide-sense stationary signal β in which the nonzero

elements |β i | ≥ λ is n > max{f 1 (p, k, λ), ... , f k (p, k, λ), k} (4.10)
where

f m (p, k, λ) = log p-k+m m -1 -1 1 2 log 1 + m e λ 2 1 -m p-k+m (4.11)
for m = 1, ... , k.

For the sake of completeness and comparison, the necessary condition by

i | ≥ λ is n > max{f 1 (p, k, λ), ... , f k (p, k, λ), k} (4.12)
where

f m (p, k, λ) = log p-k+m m -1 1 2 log 1 + mλ 2 1 -m p-k+m (4.13)
for m = 1, ... , k.

INFORMATION-THEORETIC CONDITIONS 105

In Table 4.1 the given result for strictly sparse signals is compared with the sufficient condition in [START_REF] Rad | Nearly sharp sufficient conditions on exact sparsity pattern recovery[END_REF] and the necessary condition in [START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF]. In this table, the first three rows represent the constraints for linear sparsity regimes2 .

The last three rows of the table show the constraints for sublinear regimes3 . In the last two rows the signal-to-noise ratio tends to infinity , i.e, kλ 2 → ∞.

Corollary 1 is obtained by loosening further the information rate lower bound with respect to right-hand side of (4.9) in Theorem 4. In spite of this, as demonstrated in Table 4.1, Corollary 1 is as tight as previous sufficient and necessary results. From this, it can be concluded that Theorem 4 may be asymptotically tighter than the results in [START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF][START_REF] Rad | Nearly sharp sufficient conditions on exact sparsity pattern recovery[END_REF].

The given tight sufficient condition in Corollary 1 is valid for the whole range of signal-to-noise ratio whereas the sufficient condition in [START_REF] Rad | Nearly sharp sufficient conditions on exact sparsity pattern recovery[END_REF] is claimed to be restricted to

λ 2 = Ω( 1 k ) or λ 2 = O(1) [Rad11]
. The tightness of the sufficient conditions in Theorem 4 and Corollary 1 implies that the computed condition for approximately sparse signal (in the following section) may also be tight. This is concluded because the conditions (for strictly and approximately sparse signals) are computed in the same way.

Approximately Sparse Signals

The practical signals are not strictly sparse but they are approximately sparse with a few significantly large elements and the rest is small but nonzero. In this set-up, the existing constraints based on the sparsity level may not work.

A feature of Fano's inequality is connecting the detection error probability and the mutual information rate between source and estimation random vectors. The source random vector (here it is the approximately sparse vector) does not necessarily have a discrete alphabet but the estimated vector must be drawn from a where supp k (β) is the support set that is uniformly chosen from p k subsets of size k [START_REF] Wainwright | Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting[END_REF][START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF].

In this problem, a similar approach to strictly sparse signals is used. The combination of Jensen and Minkowski inequalities is used to obtain a lower bound on the expected information rate in (4.8). For the approximately sparse signals, it may not be possible to compute the autocorrelation matrix from (p, n, k) and λ can not generally be assumed constant. A lower bound on the volume of the polytope defined by the autocorrelation matrix can be alternatively computed from the signal power spectrum [START_REF] Hayes | Statistical Digital Signal Processing and Modeling[END_REF]. Therefore, the power spectrum of the signal is assumed to be available through measurement and estimation. Having the power spectrum of the signal, the computation of the sufficient condition in the following theorem is straightforward.

Proof

Theorem 4

To obtain the exact support recovery conditions on the number of measurements, Fano's inequality is exploited A p×n and B n×p [START_REF] Meyer | Matrix Analysis and Applied Linear Algebra[END_REF]. This is an algebraic equality that implies equality of the volumes. This is required to separate the autocorrelation matrix from the sampling matrix and its conjugate transpose that faciliates the computation of the information rate. Therefore, (4.20) can be rewritten as

I (θ; Ỹ ) = 1 2 log I p-k+m + X † X R β . (4.21) rank( X † X R β ) ≤ min{rank( X † X ), rank(R β )}.
In [START_REF] Feng | The rank of a random matrix[END_REF] it is shown that rank(X † X ) = n, which implies min{rank(X † X ), rank(R β )} = n.

A lower bound on the mutual information is computed by applying Brunn-Minkowski inequality [START_REF] Cover | Elements of Information Theory[END_REF], Substituting left-hand side of (4.32) and (4.28) in (4.23) gives Theorem 6

I (θ; Ỹ ) ≥ n 2 log 1 + | X † XR β | 1/n = n 2 log 1 + exp 1 n log | X † X R β | .
E X I (θ; Ỹ ) ≥ n 2 log 1 + n Γ(n) p -k + m -1 n -1 (1 - m p -k + m ) m p -k + m λ 2 .
In proof of Theorem 4 it is assumed that β is strictly sparse. Where the signal is not strictly sparse it may not be tractable to compute analytically a lower bound on Chapter 5

Discussion and Conclusion

The first part of this report was dedicated to the presentation and analysis of a new neural network able to store a large amount of sparse messages and to retrieve them from partial and/or distorted versions. The simulation results showed that we can store a significant fraction of M max in the network (we can reach efficiencies as high as 30% with low recovery error but this depends on the different parameters).

It can be concluded that the network does not offer strict optimality but something close to it. In addition to the mentioned properties, a main feature of the proposed network was plausibility. It was intended to design a network that mimics the biological and psychological features of the human neocortex.

In the second part, we were interested in compressed sensing (CS) systems, mainly through the evaluation of their feasible compression rates in presence of noise. A new tight sufficient condition for strictly sparse signals was established.

This holds for the entire signal-to-noise ratio unlike another existing condition.

The same computation technique was used to determine a sufficient condition for approximately sparse signals. To the best of our knowledge there was no such conditions for these types of signals before. It may be concluded, that this condition is also tight, because the computation procedure had been led to a tight condition before (for strictly sparse signals).

  depuis trois points: (a) la quantité d'information contenue dans la source, (b) la quantité d'information fournie au réseau depuis le message partiel, (c) la quan-tité d'information obtenue après la récupération. Il est attendu que la quantité d'information récupérée soit plus élevée que la quantité d'information donnée par le message partiel. Le différentiel du taux d'information I diff est défini comme la quantité d'information récupérée déduite de la quantité d'information donnée par le message partiel. Le réseau est ainsi appelé informatif quand le différentiel du taux d'information est positif. La discussion ci-dessus implique que le différentiel du taux d'information soit dépendant du nombre de sous-messages manquants ainsi que du nombre de messages stockés. En effet, le taux d'information des messages partiels est fonction de ces deux facteurs. Ceci conduit à un jeu de contraintes sur le réseau afin qu'il demeure informatif, c'est-à-dire, I diff > 0. De plus, l'inégalité de Fano est aussi utilisée pour dériver les contraintes appliquées au nombre de sous-messages manquants. Dans le quatrième chapitre, une nouvelle technique d'acquisition de messages parcimonieux, à savoir compressed sensing, est étudiée du point de vue de la théorie de l'information. Différentes techniques sont utilisées pour compresser et stocker les signaux parcimonieux. Ces différentes techniques comprennent entre autres, la compression Sample-then-Compress Framework (SCF) et la compression Compressed-Sensing (CS). La première est une compression bien connue, employée notamment dans le standard de compression d'image Joint Photographic Expert Group (JPEG). Dans la compression SCF, un dispositif échantillonne un signal (incluant des informations redondantes) pour ensuite, dans une étape de post-traitement, extraire les informations importantes. CS est un domaine émergent de compression et d'acquisition de signaux dans lequel l'échantillonnage et la compression conjoints de signaux parcimonieux vise à réduire la complexité des encodeurs. Dans ce schéma, l'échantillonnage et la compression ne sont pas des procédures distinctes (c-à-d, opérées en série), mais sont réalisées simultanément. La compression CS permet d'éviter l'acquisition et le traitement d'informations redondantes : le taux d'échantillonnage est proportionnel à la teneur en informa-tions sous-jacentes (autrement dit le niveau de parcimonie) plutôt qu'à la bande passante.

  Blind Recovery . . . . . . . . . . . . . . . . . . . . . . . . 56 Variable Order Messages . . . . . . . . . . . . . . . . . . . 60 2.5.2 Blurred Messages . . . . . . . . . . . . . . . . . . . . . . 62 2.5.3 Set Implementation . . . . . . . . . . . . . . . . . . . . . 64 2.6 Optimal Network . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.6.1 Optimal Constant Message Order . . . . . . . . . . . . . . 67 2.6.2 Optimal Density . . . . . . . . . . . . . . . . . . . . . . . 68 2.6.3 Optimal Variable Message Order . . . . . . . . . . . . . . 69 Information-Theoretic Analysis of the Neural Network Memory 71 3.1 Analysis of the Message Source . . . . . . . . . . . . . . . . . . . 72 3.2 Channel Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.3 Source-Channel Coding . . . . . . . . . . . . . . . . . . . . . . . 76 3.4 Communication Channel Model . . . . . . . . . . . . . . . . . . . 78 3.4.1 Puncturing Block Channel Model . . . . . . . . . . . . . . 81 3.4.2 Neural Network Memory Channel Model . . . . . . . . . . 84 3.4.3 Recovery Constraints: Differential Information Rate . . . . 84 3.4.4 Recovery Constraints: Fano's Inequality . . . . . . . . . . . 87 3.4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Information-Theoretic Constraints on Sparse Pattern Recovery 91 4.1 Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.1.1 Restricted Isometry Property (RIP) . . . . . . . . . . . . . 95 4.1.2 Null-Space Property (NSP) . . . . . . . . . . . . . . . . . 96 4.1.3 Verification of the Algebraic Conditions . . . . . . . . . . . 96 4.2 Compressed Sensing and Neural Networks . . . . . . . . . . . . . . 97 4.3 Information-Theoretic Conditions . . . . . . . . . . . . . . . . . . 99 4.3.1 Bounds and Recovery Conditions . . . . . . . . . . . . . . 101 Strictly Sparse Signals . . . . . . . . . . . . . . . . . . . . 102 CONTENTS 13 Approximately Sparse Signals . . . . . . . . . . . . . . . . 4.3.2 Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theorem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . Corollary 1 . . . . . . . . . . . . . . . . . . . . . . . . . . Theorem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . Corollary 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Discussion and Conclusion Bibliography List of Figures 1.1 Block diagram representation of nervous system. . . . . . . . . . . . . 1.2 Diagram of a single-layer feedforward neural network. . . . . . . . . . 1.3 Diagram of a single-layer recurrent neural network with only one feedback. 2.1 The neural network inspired by the human neocortex. The dots represent the microcolumns and the regions surrounded with dashed lines show the columns (clusters) and a macrocolumn (the network) in the neocortex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 A clique (a complete subgraph) that represents a message containing eight sub-messages in the network. This clique has twenty-eight connections. Although a single loop graph with only seven connection can associate the fanals, a fully connected graph provides robustness against deficiencies. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 A network composed of 9 clusters of 16 fanals each. A message with message order 4 forms a clique in the network. . . . . . . . . . . . . . 2.4 The network density for four values of c as a function of the number of stored messages M where χ = 100 and ℓ = 64. . . . . . . . . . . . 2.5 The network diversity (η = 1) is depicted for various values of ℓ when χ = 100 and when the stored messages have a constant order 4 ≤ c ≤ χ. List of Figures 2.6 A fanal is modeled similar to McCulloch-Pitts model of neuron. It computes the sum of the received signals which is known as activity level. Thereafter, if it is equal to the maximum of the maximum activity level in the network and the threshold, it fires. . . . . . . . . . . . . . 48 2.7 A bipartite graph that represents an LDPC code is depicted. The nodes on top are variable nodes and the nodes in the bottom are check nodes. The check nodes are arithmetic nodes (that do not take values) whereas the variable nodes hold the result of iterative computation that is performed in each iteration. . . . . . . . . . . . . . . . . . . . . . . 49 2.8 A situation is demonstrated where three active fanals in a cluster send signals to a fanal in a different cluster. Since for a clique there is only one active fanal in a cluster the signal strength of each active fanal is normalized to get a total signal strength equal to unity. . . . . . . . . 52 2.9 An example of ambiguity in the network where a fanal (corresponding to a sub-message) is missing. The ambiguous fanals are connected to the known fanals with dashed lines. . . . . . . . . . . . . . . . . . . . 54 2.10 A situation in the network that cause fanal activity oscillation. This is when the fanals indicated with star markers are activated in odd iteration steps and deactivated in even iteration steps. . . . . . . . . . 58 2.11 Type III error rate is compared to total error rate for a network with χ = 100 clusters and ℓ = 128 fanals in each cluster. The partial messages have two unknown sub-messages c e = 2. It is observed that over 30% are Type III errors. . . . . . . . . . . . . . . . . . . . . . . 60 2.12 The retrieval error rate of both blind and guided recovery of M i.i.d. messages. The network has χ = 100 clusters and ℓ = 64 fanals in each cluster. The partial messages have c e = 3 unknown sub-messages. . . . 61 List of Figures 2.13 The retrieval error rate of both blind and guided recovery of M i.i.d. messages. The network has χ = 100 clusters and ℓ = 64 fanals in each cluster. The partial messages have c e = c/4 unknown sub-messages, i.e., ǫ = 0.25. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.14 The retrieval error rate of messages that are distorted by permutation. The network has χ = 100 clusters and ℓ = 64 in each cluster. The stored i.i.d. messages have order c = 12. . . . . . . . . . . . . . . . . 2.15 The set implementation error rate as a function of the density of the network composed of χ = 100 clusters of ℓ = 64 fanals each, with cliques of order c = 6 or 9. Densities corresponding to efficiency-1 diversities (M max ) are also indicated. . . . . . . . . . . . . . . . . . . 2.16 The number of stored messages is depicted for the network with χ = 100 clusters and ℓ = 64 fanals in each cluster. The curves are given for several blind retrieval error probabilities where ǫ = 0.25. . . . . . . 2.17 The message order pairs are depicted for the network with d = 0.5, χ = 100 clusters and ℓ = 64 fanals in each cluster. The curves are given for several blind retrieval error probabilities where ǫ = 0.25. The least error probabilities are given in the legend and their corresponding pair has filled marker. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Communication Channel Model . . . . . . . . . . . . . . . . . . . . . 3.2 Information-theoretic Block Diagram . . . . . . . . . . . . . . . . . . 3.3 Discrete Memoryless Erasure Channel (DMEC) diagram for the puncturing block. The information flow is from left to right. . . . . . . . . 3.4 Discrete Memoryless Erasure Channel (DMEC) diagram for the neural network memory. The information flow is from left to right. . . . . . . 3.5 Differential Information Rate I diff versus Number of Stored Messages M is illustrated for the network with χ = 100 and ℓ = 64. ǫ = 0.25 and c = 12. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Upper bounds on P e exploiting the DMEC model for the network. The network has χ = 100 clusters, ℓ = 64 fanals in each cluster. The stored messages' order is c = 12. . . . . . . . . . . . . . . . . . . . . 3.7 Upper bounds on P e for the network with χ = 100, ℓ = 64 and c = 12. 4.1 Compressed-sensing has been modeled as a single-layer neural network. The connections have random i.i.d. Gaussian weights. . . . . . . . . .

4. 1

 1 Sufficient and Necessary Conditions on n for Exact Support Recovery in the Linear and the Sublinear Regimes. The sufficient condition in [Rad11] holds only for λ 2 = Ω( 1 k ) or λ 2 = O(1) whereas the other sufficient and necessary conditions hold for the entire signal-to-noise ratio range. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  and Working Memory [BH74] models. The Working Memory model is proposed by Baddeley and Hitch and describes Short-Term Memory (STM) and its mechanisms. The model proposed by Atkinson and Shiffrin consists of Sensory Memory (SM), STM and Long-Term Memory (LTM) stages. Sensory memory describes the first few hundred milliseconds after informative items are perceived. Short-term memory refers to the first few seconds after the items are perceived. Long-term memory describes the memory's ability to remember what is learned after a long time from several minutes after informative items are perceived to much longer. Apart from

Figure 2 . 1 :

 21 Figure 2.1: The neural network inspired by the human neocortex. The dots represent the microcolumns and the regions surrounded with dashed lines show the columns (clusters) and a macrocolumn (the network) in the neocortex.

Figure 2

 2 Figure 2.2: A clique (a complete subgraph) that represents a message containing eight sub-messages in the network. This clique has twenty-eight connections. Although a single loop graph with only seven connection can associate the fanals, a fully connected graph provides robustness against deficiencies.

Figure 2

 2 Figure 2.3: A network composed of 9 clusters of 16 fanals each. A message with message order 4 forms a clique in the network.

  ) where w has size |C | × |F | × |C | × |F |. Such matrix representation of graph connections compresses the information (where the network is built and simulated).

NFigure 2

 2 Figure 2.4: The network density for four values of c as a function of the number of stored messages M where χ = 100 and ℓ = 64.

  Me s s age Or de r ( c ) Dive r s ity ( M m a x ) ℓ = 64 ℓ = 128 ℓ = 256 ℓ = 512 ℓ = 1024

Figure 2 . 5 :

 25 Figure 2.5: The network diversity (η = 1) is depicted for various values of ℓ when χ = 100 and when the stored messages have a constant order 4 ≤ c ≤ χ.

  (a) Accumulating received signals from the connected fanals to each one. (b) Applying Winner-take-all (see section 2.4.1) in order to determine the active fanals in the network. (c) repeating steps (a) and (b) iteratively until the network converges or for a limited iteration steps. (d) detect whether the remaining active fanals (after the last iteration step) construct a unique clique while there is only one active fanal in each cluster. Assume the network has stored a message set M and is stimulated with a particular input. Now consider the connection matrix w in (2.3) which is four 2.4. RETRIEVAL 51 dimensional. In step (a) the network computes the accumulated received signals from clusters with index 1

Figure 2 . 9 :

 29 Figure 2.9: An example of ambiguity in the network where a fanal (corresponding to a sub-message) is missing. The ambiguous fanals are connected to the known fanals with dashed lines.

  of the original message is unknown has to investigate the entire network. Assume the messages in the stored message set have order c and partial messages have c e missing clusters each. The sufficient condition for message m to be certainly recovered from its partial message is that there are no fully connected irrelevant fanals to the known fanals. The network dynamics in the first iteration activates those fanals that are connected to all cc e known fanals. Thus, if any other 2.5. PERFORMANCE 57 fanals in the network has less than cc e connections with the known fanals, the network converges to the right clique in the first iteration.The probability of having a connection between two fanals in two distinct clusters is approximately equal to the network density P ≈ d. Therefore, a single connection in the network can be considered as a random variable with Bernoulli distribution whose success probability is d.

  the fanals indicated with black markers. The network dynamics activate two other fanals in the first iteration that are indicated with star markers. The message clique corresponding to the stored message is depicted with solid lines and includes one of the activated fanals indicated with a star in the first iteration. The second star marker is an activated fanal that belongs to another stored message. Assume the 2.5. PERFORMANCE 59 network passes to the second iteration step. At the end of this step, the fanals indicated with star markers are deactivated and only the fanals that were initially activated by the stimulus (the partial message) remain active. Thus, in case the recovery passes to the next iteration steps the network oscillates between two distinct states: (a) only the partial message fanals are activated. (b) the partial message fanals along with the two other fanals (that are connected to all partial message fanals) indicated with star marker are activated. Therefore, the network never converges and it does not recover the stored message. This is so-called Type III error that is the third kind of introduced errors along with Type I and Type II errors. Assume that in Fig. 2.10, the network has stored message m = [4, -, 7, -, -, 5, 3, -, -].

N

  umb e r of s t or e d me s s age s ( M ) R e t r ie val Er r or R at e De c od. 1 I t e r . Blind De c od. ( T he o.) Guide d De c od. 1 I t e r . Guide d De c od. ( T he o.) Guide d De c od. 4 I t e r .

Figure 2 .

 2 Figure 2.12: The retrieval error rate of both blind and guided recovery of M i.i.d. messages. The network has χ = 100 clusters and ℓ = 64 fanals in each cluster. The partial messages have c e = 3 unknown sub-messages.

N

  Figure 2.13: The retrieval error rate of both blind and guided recovery of M i.i.d. messages. The network has χ = 100 clusters and ℓ = 64 fanals in each cluster. The partial messages have c e = c/4 unknown sub-messages, i.e., ǫ = 0.25.

N

  Figure 2.14: The retrieval error rate of messages that are distorted by permutation. The network has χ = 100 clusters and ℓ = 64 in each cluster. The stored i.i.d. messages have order c = 12.

  De ns ity ( d ) Probability of accepting a random message c = 6 ( Simulat ion) c = 6 ( T he or e t ic al) c = 9 ( Simulat ion) c = 9 ( T he or e t ic al) M m a x ≈ 3 × 10 5 M m a x ≈ 2 × 10 5

Figure 2 .

 2 Figure 2.15: The set implementation error rate as a function of the density of the network composed of χ = 100 clusters of ℓ = 64 fanals each, with cliques of order c = 6 or 9. Densities corresponding to efficiency-1 diversities (M max ) are also indicated.

Figure 2

 2 Figure 2.16: The number of stored messages is depicted for the network with χ = 100 clusters and ℓ = 64 fanals in each cluster. The curves are given for several blind retrieval error probabilities where ǫ = 0.25.

MFigure 2

 2 Figure2.17: The message order pairs are depicted for the network with d = 0.5, χ = 100 clusters and ℓ = 64 fanals in each cluster. The curves are given for several blind retrieval error probabilities where ǫ = 0.25. The least error probabilities are given in the legend and their corresponding pair has filled marker.

m

  1 = [-, 12, -, 14, -, 78, 35, -] and m 2 = [-, 15, -, 14, -, 78, 35, -]. NETWORK MEMORY Consider that the first non-blank sub-message in m 1 is randomly missing (c e = 1).

Definition 5 .

 5 A code (M, c) of length c and cardinality M over an alphabet A is a collection of M elements from A c . The elements of the code are called codewords [RU08, LC04].

  12, -, 14, -, 78, 35, -] and m 2 = [-, 15, -, 14, -, 78, 35, -]

CHAPTER 3 .

 3 INFORMATION-THEORETIC ANALYSIS OF THE NEURAL NETWORK MEMORY parameter, namely minimum Hamming distance. It is the minimum number of non-identical elements in two distinct codewords of a code. A larger Hamming distance implies a stronger code (in terms of error detection and correction). Hamming distance is the minimum Euclidean distance between two codewords and the network does not have an algebraic topology. Therefore, it does not characterize the clique codes. Assume two cliques that only have one different sub-message.

Figure 3 Figure 3

 33 Figure 3.1: Communication Channel Model

Figure 3 . 3 :Figure 3

 333 Figure 3.3: Discrete Memoryless Erasure Channel (DMEC) diagram for the puncturing block. The information flow is from left to right.

NFigure 3 . 6 :

 36 Figure 3.5: Differential Information Rate I diff versus Number of Stored Messages M is illustrated for the network with χ = 100 and ℓ = 64. ǫ = 0.25 and c = 12.

Fano's inequality

  is one of the information-theoretic utilities that are often used to compute bounds and constraints [CT06, Chapter 2]. Fano showed that for any two random variables y and w, inequality H(p) + pH(w) ≥ H(w|y) (3.10) holds where p = Pr[y = w]. This variation of Fano's inequality given in [CT06, p. 39] is used to compute the constraints in this section. The importance of Fano's inequality lies in the connection of the error probability with the information rate. Theorem 1. Assuming I (m; m) < I (m; m), the network holds I (m; m) ≥ (1 -P e )H(m) -H(P e ) (3.11) where P e = Pr[m = m].

Figure 3 . 7 :

 37 Figure 3.7: Upper bounds on P e for the network with χ = 100, ℓ = 64 and c = 12.

Figs. 3

 3 Figs. 3.7 and 3.6 show that Theorem 1 gives a tighter bound than (3.9) and (3.8).

  scheme for which Joint Photographic Experts Group (JPEG) image compression standard is an example. In SCF, a device samples a real-world signal (including redundant information), then, in a post processing stage, it extracts useful information. Assume p-dimensional vector α is acquired through a sampling process that satisfies Nyquist criterion. Further assume α is sparse in a basis indicated by B and the complete set of transform coefficients {β i } is computed as β = Bα. The k largest coefficients in β are located and the pk smallest coefficients are discarded. The values and locations of those large coefficients are encoded and

(P 0

 0 ) minimize |supp(α)| subject to XB α = Y , where supp(.) gives the support set of a vector. This optimization problem is nonpolynomial (NP) time in general. In [CT05, Don06, CW08], Candès and Donoho show that under Restricted Isometry Property (RIP) and Null-Space Property (NSP) conditions, the solution of

96CHAPTER 4 .

 4 INFORMATION-THEORETIC CONSTRAINTS ON SPARSE PATTERN RECOVERYhave their eigenvalues in [1δ k , 1 + δ k ] and the k-sparse vectors can not be in the null-space of X τ [YZ09, CW08].

  that is a set of indices where elements of β are nonzero. The estimation of β as a function of X and Y is an inverse problem that consists of (a) detecting the support and (b) estimating the amplitudes of the nonzero elements[START_REF] Akcakaya | Shannon-theoretic limits on noisy compressive sampling[END_REF][START_REF] Rad | Nearly sharp sufficient conditions on exact sparsity pattern recovery[END_REF].100 CHAPTER 4. INFORMATION-THEORETIC CONSTRAINTS ON SPARSE PATTERN RECOVERYOnce the support set of β is determined, the estimated sparse (optimal) solution isβ = arg min ν ||Y -X supp( β) ν|| 2 2 (4.5)where X supp( β) is a n×k sub-matrix of the measurement matrix with column indices in supp( β). Therefore, as it is discussed in [AT10, Rad11, WWR10], finding the optimal solution of such a noisy system is reduced to the exact support recovery.The error metric is the 0-1 loss function defined in [Wai09, WWR10, AT10]ρ(β, β) = I βi = 0, ∀i ∈ supp(β) ∩ βj = 0, ∀j ∈ supp(β)(4.6) where I(.) is the indicator function. A decoder D : Y → θ maps the vector Y to a support set θ = supp( β). The probability of choosing a wrong support set is Pr[θ = supp(β)|X , β] over the measurement noise and the sampling matrix. The average detection error is defined as in [Wai09, WWR10] P err = 1 p k Pr[D(Y ) = supp(β)|X , β] where the support supp(β) is assumed to be chosen uniformly random from p k possible subsets of size k [Wai09, WWR10]. In an exact support recovery regime, the aim is to have asymptotically zero average detection error where P err → 0 as n → ∞ [Wai09, WWR10].

4. 3 .

 3 INFORMATION-THEORETIC CONDITIONS 101 of a k-sparse vector is not solely guaranteed by its SNR [WWR10, Rad11]. The case in which the decoder has the highest failure probability for a given SNR is considered, by taking |β i | = λ where i ∈ supp(β) and λ is the minimum absolute value of any nonzero element of the strictly sparse vector β. Therefore, by such assumption, the recovery of any k-sparse vector with SNR ≥ kλ 2 is guaranteed [Wai09, WWR10, Rad11].

FRG09]

  are dedicated to strictly sparse signals. These signals have explicitly k nonzero elements and the rest are zeros.The tightness of the recovery constraints through (4.8) depends on its righthand side that is E X I (θ; Y ) (see[START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF][START_REF] Aeron | Information theoretic bounds for compressed sensing[END_REF]). To compute the information rate, the autocorrelation matrix of the sparse vector is required (see[START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF][START_REF] Aeron | Information theoretic bounds for compressed sensing[END_REF][START_REF] Sarvotham | Measurements vs. bits: Compressed sensing meets information theory[END_REF]). In general, the autocorrelation matrix is computed from the probability distribution function (PDF) of the process. The distribution function may not always be known and assuming a specific PDF restricts the given constraint to that specific random process. Therefore, in[START_REF] Sarvotham | Measurements vs. bits: Compressed sensing meets information theory[END_REF][START_REF] Aeron | Information theoretic bounds for compressed sensing[END_REF] an upper bound on I (θ; Y ) is computed and exploited to obtain their recovery constraints. In[START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF], the authors compute a tighter upper bound (with respect to[START_REF] Sarvotham | Measurements vs. bits: Compressed sensing meets information theory[END_REF][START_REF] Aeron | Information theoretic bounds for compressed sensing[END_REF]) on the information rate that results in tighter necessary conditions on the exact support recovery.When the process is ergodic and wide-sense stationary (EWSS), the autocorrelation function and consequently the autocorrelation matrix can be computed from its time realizations[START_REF] Papoulis | Probability, Random Variables and Stochastic Processes[END_REF][START_REF] Hayes | Statistical Digital Signal Processing and Modeling[END_REF]. The random sparse vector is chosen uniformly from p k possible k-sparse vectors of dimension p in which a vector element is nonzero with probability k/p [Pap91,[START_REF] Baron | Universal map estimation in compressed sensing[END_REF][START_REF] Shihao | Bayesian compressive sensing[END_REF]. This is employed4.3. INFORMATION-THEORETIC CONDITIONS103 in[START_REF] Baron | Universal map estimation in compressed sensing[END_REF][START_REF] Shihao | Bayesian compressive sensing[END_REF] to compute different statistics and sparse signals. EWSS assumption is exploited to compute the autocorrelation matrix for the worst case scenario (where |β i | = λ ∀i ∈ supp(β)) without having knowledge of PDF. Having the autocorrelation function, the exact information rate can be computed for the worst case scenario EWSS signals. What remains as an obstacle is the computation of the expected information rate in (4.8) with respect to sampling matrix X (for which only its distribution is known). To overcome that, the combination of Jensen and Minkowski inequalities is exploited to obtain a lower bound on E X I (θ; Y ). It is worth mentioning that the combination of Jensen and Minkowski inequalities for the information rate results in extremely tight bounds that is reported in[START_REF] Oyman | Tight lower bounds on the ergodic capacity of Rayleigh fading MIMO channels[END_REF][START_REF] Shi | Tight lower bounds on the ergodic capacity of ricean fading MIMO channels[END_REF]. This combination is of great importance. It facilitates the information rate computation through product of two polytopes' volumes. The first is a Wishart matrix (that defines a polytope) constructed from the Gaussian sampling matrix and the second is the autocorrelation matrix of the worst case ergodic wide-sense stationary signal. This tight lower bound on the expected information rate is used in (4.8) to get a sufficient condition depending on (p, n, k, λ) which is given in the following theorem.

106

  CHAPTER 4. INFORMATION-THEORETIC CONSTRAINTS ON SPARSE PATTERN RECOVERY discrete and countable alphabet [CT06]. This plays an important role in computation of recovery conditions for approximately sparse signals. Assume that the wide-sense stationary and approximately sparse random vector β has k significantly large elements and the rest are small and the support detector recovers the k largest elements. To obtain recovery conditions for the approximately sparse signals assume decoder D : Y → θ where θ is a detected support set with cardinality k. The support set of an approximately sparse signal is defined to be the indices of the k largest elements supp k (β) {i :β i = 0, β i > β j > β p , k + 1 ≤ j ≤ p}.The error metric is defined asρ k (β, β) = I βi = 0, ∀i ∈ supp k (β) ∩ βj < β k , ∀j ∈ supp k (β)(4.14) where β k is the kth largest element of β. The probability of choosing a wrong support set is Pr[θ = supp k (β)|X , β] and the average detection error is P e = 1 p k Pr[D(Y ) = supp k (β)|X , β]

  4.3. INFORMATION-THEORETIC CONDITIONS107Theorem 6. Assume a measurement matrix X ∈ R n×p whose elements are drawn from the outcome of an i.i.d. Gaussian random source with zero mean and unit variance, i.e., X i,j ∼ N (0, 1). A sufficient condition for asymptotically reliable recovery of a wide sense-stationary sparse signal β with k large nonzero elements islog pk + m m -G n Γ(n) pk + m -1 n -1 (4.16)in which Γ(.) is Gamma function, m = 1, ... , k and G is the infimum of the approximately sparse signal power spectrum.Corollary 2. Assume k = Θ(p). In Theorem 6 the sufficient condition for asymptotically reliable recovery of a wide-sense stationary and approximately sparse signal β is obtained by replacing 16) where S(ω) is the power spectrum of the sparse signal.

  θ; Y ) is the mutual information between θ and Y [Wai09,WWR10,ASZ10, CT06]. θ is the detected support set that is given by the decoder, θ = D(Y ). P e is the probability that the decoder fails to detect the correct support set, i.e.,P e = Pr[supp(β) = θ|X , β]. PATTERN RECOVERY Scaling Sufficient Condition Corollary 1 Necessary Condition Theorem 5 [WWR10] Sufficient Condition [Rad11] k = Θ(p) λ 2 = Θ( 1 k ) n = Θ(p log p) k = Θ(p) λ 2 = Θ( log k k ) n = Θ(p) k = Θ(p) λ 2 = Θ(1) n = Θ(p) k = o(p) λ 2 = Θ( 1 k ) n = Θ(k log(pk)) k = o(p) λ 2 = Θ( log k k ) n = max Θ( k log(p-k) log k), Θ(k log p k log log k ) k = o(p) λ 2 = Θ(1) n = max Θ( k log p k log k ), Θ(k)Table 4.1: Sufficient and Necessary Conditions on n for Exact Support Recovery in the Linear and the Sublinear Regimes. The sufficient condition in [Rad11] holds only for λ 2= Ω( 1 k ) or λ 2 = O(1)whereas the other sufficient and necessary conditions hold for the entire signal-to-noise ratio range.The error probability of the decoder, P err (D), is the average error probability with respect to Gaussian measurement matrix X . This is P err (D) = E X P e where E X denotes the expected value operator with respect to X [AT10,WWR10]. Further, assume that the decoder has a priori knowledge of all nonzero locations of β but m locations with smallest values (1 ≤ m ≤ k). The decoder has to choose from p-k+m m support sets [WWR10]. Let U be the set of unknown location indices where |U| = m. The n-dimensional observation vector is Ỹ = X β + W where X is the measurement matrix with column indices in U . β is the vector subject to measurement with element indices in U . Therefore, the error probability of the decoder is bounded as P err (D) ≥ 1 -E X I (θ; Ỹ ) + log 2 log p-k+m m -1 . (4.19)

4. 3 .

 3 INFORMATION-THEORETIC CONDITIONS109The mutual information I (θ; Ỹ ) is given byI (θ; Ỹ ) = H( Ỹ | X ) -H( Ỹ |θ, X ) = H( Ỹ | X ) -H(W ) = 1 2 log I n + X R β X † (4.20)where R β is the autocorrelation matrix of random vector β and † indicates Hermitian transpose. The equality |I p + AB| = |I n + BA| holds for any pair of matrices

  taking the expectation in (4.22) and by using Jensen's inequalityE X I (θ; Ỹ ) σ i R β . (4.25) 110 CHAPTER 4. INFORMATION-THEORETIC CONSTRAINTS ON SPARSE PATTERN RECOVERY σ i (.) is the ith eigenvalue of a matrix. In (4.25), the eigenvalues are sortedσ 1 (R β ) < σ 2 (R β ) < • • • < σ p-k+m (R β ).

( 4 .

 4 24) is the expected value of the logarithm of random Wishart matrix determinant | X † X |. The product of the eigenvalues of this random Wishart matrix is distributed as product of n chi-square distributed random variables [YL03, logarithm and then the expectation of the right-hand side of (4.26)a = E n j=1 log χ 2 p-k+m-j+1 = -nγ +where γ is Euler's constant[START_REF] Kim | On the log determinant of noncentral wishart matrices[END_REF][START_REF] Oyman | Tight lower bounds on the ergodic capacity of Rayleigh fading MIMO channels[END_REF]. In the asymptotic regime whereP e (D) → 0 as n → ∞ that implies p → ∞ pk + mj) . a = n j=1 log(pk + mj) = log(pk + mj -1)!log(pk + mn -1)! = log Γ(pk + m) Γ(pk + mn) = log Γ(pk + m) Γ(n)Γ(pk + mn) Γ(n) = log pk + m -1 n -1 + log Γ(n) (4.28)where Γ(.) is Gamma function. The sparse vector elements βi is modeled as output of an ergodic wide-sense stationary random vector source. Therefore, the elements of such random vector is also ergodic wide-sense stationary. The nonzero elements appear with probability Pr[ βi = 0] = m p-k+m [Pap91,BSB10,SXC08]. The autocorrelation matrix of β is a Hermitian Toeplitz matrix that is obtained from its autocorrelation function[START_REF] Hayes | Statistical Digital Signal Processing and Modeling[END_REF]. Assume that the nonzero elements βi where 4.3. INFORMATION-THEORETIC CONDITIONS 111 i ∈ U , are negative with probability ξ, i.e., ξ = Pr[ βi ∈ R -]. The autocorrelation function at lag τ = 0 isr β (0) = 1 pk + m i βi βi = m pk + m λ 2 .For lag τ = 0 and |τ | ≤ p, the autocorrelation function isr β (τ ) = 1 pk + m i βi βi+τ = pk + m -|τ | pk + m ( m pk + m ) 2 λ 2 × ξ 2 + (1ξ) 2 -2ξ(1ξ) .For |τ | > p the autocorrelation function r β (τ ) = 0. Therefore, the autocorrelation function isr β (τ ) =              (p-k+m-|τ |)m 2 (p-k+m) 3 (4ξ 2 -4ξ + 1)λ 2 if |τ | ≤ p,of β is a Hermitian Toeplitz matrix with r β (τ ) in its first row, i.e., R β = Toeplitz{r β }.R β and r β is used to find a lower bound on (4.25),n log σ min ≤ n i=1 log σ i R β where σ min ≤ σ i (R β )is the lower bound on all eigenvalues of R β . The minimum eigenvalue of R β is lower bounded by the infimum of the power spectrum[START_REF] Hayes | Statistical Digital Signal Processing and Modeling[END_REF],σ min = min ω S β (ω) (4.29)whereS β (ω) = sin(ω(p + 1/2)) sin(ω/2) 2 ( m pk + m λ) 2 (4ξ 2 -4ξ + 1) + m pk + m λ 2 -( m pk + m λ) 2 (4ξ 2 -4ξ +1) (4.30) 112 CHAPTER 4. INFORMATION-THEORETIC CONSTRAINTS ON SPARSE PATTERN RECOVERY is the power spectrum of β. It is computed by taking Fourier transform of r β [Hay96]. Therefore, σ min (ξ) = m pk + m -( m pk + m ) 2 (4ξ 2 -4ξ + 1) λ 2 (4.31) from (4.30) and (4.29). σ min is a function of ξ. The term 0 ≤ 4ξ 2 -4ξ + 1 ≤ 1 reaches its maximum when ξ ∈ {0, 1}, i.e., the sparse vector subject to measurement is unipolar. To lower bound the minimum eigenvalue ξ is chosen either 0 or 1, ξ ∈ {0, 1}, that results in b ≥ n log (1 -m pk + m ) m pk + m λ 2 . (4.32)

  In proof of Theorem 4a = log pk + m -1 n -1 + log Γ(n) (4.36)that can be lower bounded to obtain another lower bound on E X I (θ, Ỹ ). On the other hand2π(n -1)(n -1) (n-1) e -(n-1) ≤ Γ(n) (4.37)and(n -1) log pk + m -1 n -1 ≤ log pk + m -1 n -1 . (4.38)Considering n → ∞ (see the asymptotic Fano's inequality in[START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF]) andconsequently p → ∞ a/n ≥ (n -1) n log pk + m -1 n -1 + 1 n log 2π(n -1)(n -1) (n-1) e -(n-1) ≥ n -1 n log(pk + m -1) -n -1 n .(4.39)By replacing the right-hand sides of (4.39) and (4.32) in (4.23)

( 4 .

 4 25) as it is computed in Theorem 4. In the proof of Theorem 4 a lower bound on b is obtained through computation of a lower bound on the minimum eigenvalue of the signal autocorrelation matrix. The minimum eigenvalue of the autocorrelation matrix of the signal is lower bounded by the infimum of the power spectrum (see[START_REF] Hayes | Statistical Digital Signal Processing and Modeling[END_REF] for details). Assume that the power spectrum of the approximately sparse signal is known (from experiments or from computations). By replacing σ i (R β ) with its lower bound (see (4.29) and (4.25)) that is obtained from the signal power spectrum the sufficient condition in Theorem 6 is computed. 114 CHAPTER 4. INFORMATION-THEORETIC CONSTRAINTS ON SPARSE PATTERN RECOVERY Corollary 2 Consider k = Θ(p). In (4.25) the eigenvalues of the autocorrelation matrix are sorted. They are n smallest eigenvalues out of p. To tighten the condition in Theorem 4 a lower bound in [MV97] is used on the product of n smallest eigenvalues of the matrix instead of lower bounding (4.25) by replacing the eigenvalues with the minimum eigenvalue. Therefore, a lower bound on (4.25) is computed as b≥ (pn) log pn SNR + log R β = (pn) log p -where the second term in the right-hand side is the integral of the logarithm of the signal power spectrum[START_REF] Merikoski | Bounds for eigenvalues using the trace determinant[END_REF][START_REF] Gray | Toeplitz and Circulant Matrices: A Review[END_REF]. Noting that inequalities k ≤ p and n ≥ k hold, k = Θ(p) implies that

  CHAPTER 2. SPARSE NEURAL NETWORK MEMORIES resent microcolumns in human neocortex) are the elements of the network to perform Winner-take-all. "Current data on the microcolumn indicate that the neurons within the microcolumn receive common inputs, have common outputs, are interconnected, and may well constitute a fundamental unit of the cerebral cortex" [CBP + 05]. Considering above discussions, a fanal is modeled based on the McCulloch-Pitts model [MP43]. In Fig. 2.6, the fanal model is depicted. It is Figure 2.6: A fanal is modeled similar to McCulloch-Pitts model of neuron. It computes the sum of the received signals which is known as activity level. Thereafter, if it is equal to the maximum of the maximum activity level in the network and the threshold, it fires. similar to the model proposed by McCulloch and Pitts for neurons in [MP43]. A fanal computes the sum of these received signals from other fanals in the network.

. In this report, as it was explained earlier (see section 2.1), the fanals (that rep-

≥ max(v max , σ)

The sum of received signals is so-called activity level of the fanal. A fanal fires if its activity level is equal to max(v max , σ). v max is the maximum activity level of a fanal in either a cluster (which the fanal belongs to) or all fanals in the network,

2.4. RETRIEVAL

49

  4.8)for m = 1, ... , k where k is the sparsity level, p is the sparse vector dimension and Em nonzero (or significantly large) elements. As it is discussed in[START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF], having a priori knowledge about some nonzero elements may not facilitate the support detection. In fact, for some (p, k, m) where m < k there are more support sets to choose than m = k. The cardinality of the support sets that

		CHAPTER 4. INFORMATION-THEORETIC CONSTRAINTS ON SPARSE
	102	PATTERN RECOVERY
	knows indices of k may be chosen wrongly by the support detector is p-k+m m	-1. This appears in
	the left-hand side of (4.8) that reaches a maximum value for a particular (p, k, m)

X I (θ; Y ) is the expected information rate between measurement vector Y and detected support vector θ (see

[START_REF] Aeron | Information theoretic bounds for compressed sensing[END_REF][START_REF] Wang | Informationtheoretic limits on sparse signal recovery: Dense versus sparse measurement matrices[END_REF]

). m is the number of nonzero elements that is not known by the support detector, i.e., the detector a priori

A microcolumn is also called a minicolumn[START_REF] Mountcastle | The columnar organization of the neocortex[END_REF]

A multipartite graph is a graph whose nodes are separated into disjoint sets. The edges of the graph may only be among nodes in disjoint sets of nodes, i.e., there is no edge between nodes belonging to the same set.

A maximal complete subgraph is so-called clique[START_REF] Moon | On cliques in graphs[END_REF][START_REF] Gripon | Sparse neural networks with large learning diversity[END_REF]. The storage of a sole message in the network constructs a clique.

The cluster and fanal indices are assigned by counting them in the figure from left to right and down to top.

The support of a message is the set of indices of sub-messages that are non-blank.

f (n) = Ω(g (n)) iff ∃ positive c, n 0 such that f (n) ≥ c g (n) ≥ 0 ∀n ≥ n 0 .

This phenomenon is seen easier when ℓ is large and this is why ℓ = 128 unlike other simulations that have ℓ = 64.

In the existing literature in which sparse data structures are studied[START_REF] Baraniuk | Compressive sampling[END_REF][START_REF] Candès | An introduction to compressive sampling[END_REF][START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF], sparse signal and sparse vector may be distinct. A sparse vector is a vector with a few nonzero elements whereas a sparse signal is not intrinsically sparse but it has sparse coefficients in a particular basis.

In computation of the asymptotic constraints k = Θ(p) is taken as k ≈ p, i.e., k = p -1.

In computation of the asymptotic constraints k = o(p) implies that k/p → 0, i.e., k ≪ p.

Acknowledgment

Foremost, I would like to express my gratitudes to my thesis director Prof. Claude Berrou for all his continuous help and support.

I am grateful to my parents and my brother for all their lifelong support and inspiration.

I also thank Futur et Ruptures programme of Institut Mines-Télécom that funded my Ph.D. studies.

Chapter 3 Information-Theoretic Analysis of the Neural Network Memory

Information theory is strongly related to probability theory. It was introduced first by Claude E. Shannon in 1940's to quantify information processed by a system, for which the input and output information can be modeled by probability density functions. Shannon introduced a metric, namely entropy, defined as a random variable x: x∈Ω -P(x) log P(x) where P(x) is the probability of outcome x in the probability sample space Ω. Entropy is a real and positive value that measures the amount of randomness, i.e., that reaches its maximum value when x is uniformly distributed (which represents maximum randomness) [START_REF] Shannon | A mathematical theory of communication[END_REF][START_REF] Cover | Elements of Information Theory[END_REF]. Shannon established the separate source and channel coding strategies. He considered the source coding (compression) and the channel coding (error correction) as separate blocks: information is first processed by a source coding block to remove useless redundancy. The result is then processed by a channel coding block to embed smart redundancy. This redundancy helps the receiver at recovering the original information from the distorted received information.

The situation in the brain is comparable: external stimuli coming from the outside world are compressed through successive processing layers (such as in the ing. Principal Component Analysis (PCA) and Independent Component Analysis (ICA) [START_REF] Weiss | Learning compressed sensing[END_REF] are two machine learning techniques for dimensionality reduction.

ICA and PCA methods find a basis for a known vector set in which the vectors may not be sparse. In case there are linear dependencies among the vectors, the computed basis maps the vectors to a lower dimension. This process is necessarily adaptive (because the basis is computed for a specific vector set) whereas compressed-sensing is not adaptive. On the other hand, the vectors subject to compression in ICA and PCA may not be necessarily sparse.

A compressed-sensing system may be considered as a single-layer neural network where the neural connections (weights) are i.i.d. Gaussian random values.

These weights are kept constant throughout the learning process. In Fig. 4.1, this model is illustrated. The network responds to an input vector (stimulus) by giving a lower dimensional or a higher dimensional pair of that vector. In other words, the network has intrinsically learned (in the random matrix X ) p k sparse vectors 116 CHAPTER 5. DISCUSSION AND CONCLUSION These two parts are strongly related: the purpose of the neural network is to store sparse messages with the largest possible efficiency (i.e. with the best use of available material resource) whereas the CS system is intended to transmit sparse messages spending the less possible energy (i.e. with the shortest possible length).

It was then natural to try to study the properties of the proposed network in the light of CS theory.

The CS principle can be described by a bipartite graph which associates vectors of length p with vectors of length n < p through weighted connections (cf.

Fig. 1.2). This is the simplest graphical way to describe a matrix-vector product, which can then be directly transcribed into a perceptron-like neural network. The network proposed in this report is quite different: (a) it is not an operator but a memory. (b) it has a binary structure (connections have weight 0 or 1). (c) source and channel coding are both performed by the network.

Regarding the last point, source coding comes from two features. First, any message of length χ is stored as a clique with only c vertices (c ≪ χ) for sparse messages); second, when M messages are stored, the corresponding cliques share vertices and edges, which adds to the compression rate. As for channel coding, it is assured by the strongly redundant structure of cliques.

Although the CS operation and the proposed neural network are both intended to process sparse messages, the comparison in terms of compression rate and performance is not straightforward.

To compare compressed sensing and the proposed network, consider a scenario.

The same set of sparse vectors is compressed by both systems, thereafter, the compressed information is transmitted. The main interest is finding out which one is possibly more efficient. (1) Assume a noise-free compressed sensing system along with a genie support detector. It transforms a k-sparse analog vector of length p into an analog vector of length n < p. Then, the latter is quantized on ℓ levels, thus producing a message of n log 2 ℓ bits. In a given slot of time, M such messages are compressed and sent by some communication system. The total amount of transmitted information is Mn log 2 ℓ bits.

(2) M c-sparse vectors of length χ, each character (or sub-message) being quantized on ℓ levels, are stored in the proposed neural network. Then, the communication system sends the state of the network, that is, Q = χ(χ-1)ℓ 2 2 bits. According to efficiency-1 diversity given by (2.5), an upper bound on M is

If we want the classical CS system to send as many messages as M max , with p = χ, k = c, the same level ℓ of quantization and with the same total amount of bits Q, we need Q = M max n log 2 ℓ, which leads to:

For some values of the parameters, the first term in numerator may be neglected by comparison with the second one, which then leads to a rather interesting result: n ≈ c, meaning that the classical system must achieve optimality (n of the order of c = k). Reversely, this means that the neural network may be considered as optimum as a compressed-sensing and storing unit.

Certainly, all this is approximation. Moreover, in the second situation, the messages are not ordered in the network and we have to use additional clusters to store addresses (for instance, with χ = 100, we can solve this problem, with 5 additional clusters, that is about 5% extra material).

The proposed network and compressed-sensing were both modeled as noisy communication channels. Then, they were analysed using Fano's inequality to compute the recovery conditions. Discrete Memoryless Erasure Channel (DMEC) model was used for the analysis of the network and Multiple Input Multiple Output (MIMO) noisy channel was used for compressed-sensing. Regardless of the type of channel model, Fano's inequality connects the detection error probability to the system information rate. It was observed that the computed bounds are tight: the CHAPTER 5. DISCUSSION AND CONCLUSION network bound is tighter than the given bound by I diff introduced in [SSP96] and compressed-sensing conditions are tighter than previous works.