## Analysis of Recurrent Linear Networks for Enabling Compressed Sensing of Time-Varying Signals

MohammadMehdi Kafashan, Anirban Nandi, and ShiNung Ching

## Abstract

Recent interest has developed around the problem of dynamic compressed sensing, or the recovery of timevarying, sparse signals from limited observations. In this paper, we study how the dynamics of recurrent networks, formulated as general dynamical systems, mediate the recoverability of such signals. We specifically consider the problem of recovering a high-dimensional network input, over time, from observation of only a subset of the network states (i.e., the network output). Our goal is to ascertain how the network dynamics lead to performance advantages, particularly in scenarios where both the input and output are corrupted by disturbance and noise, respectively. For this scenario, we develop bounds on the recovery performance in terms of the dynamics. Conditions for exact recovery in the absence of noise are also formulated. Through several examples, we use the results to highlight how different network characteristics may trade off toward enabling dynamic compressed sensing and how such tradeoffs may manifest naturally in certain classes of neuronal networks.

## Index Terms

Recurrent networks, linear dynamic systems, over-actuated systems, sparse input, l 1 minimization

## I. INTRODUCTION

W E consider the analysis of recurrent networks for facilitating recovery of a high-dimensional, time-varying, sparse input in the presence of both corrupting disturbance and confounding noise. The network receives an input u t and generates the observations (network outputs), y t via its recurrent dynamics, i.e.,

$$x _ { t + 1 } & = f ( x _ { t }, u _ { t }, d _ { t } ) \\ y _ { t } &$$

where, here, x t are the network states, d t is the corrupting disturbance and e t is the confounding noise. Our focus is on how the network dynamics, embedded in f ( ) · , g ( ) · , impact the extent to which u t can be inferred from y t in the case where the dimensionality of the latter is substantially less than that of the former. We will focus exclusively on the case where these dynamics are linear.

Such a problem, naturally, falls into the category of sparse signal recovery or compressed sensing (CS), for under-determined linear systems [1]-[3]. It is well known that for such problems, exact and stable recovery can be achieved under certain assumptions related to the statistical properties of the observed signal [4]-[7]. Classical CS, however, does not typically consider temporal dynamics associated with the recovery problem.

## A. Motivation

Given the natural sparsity of electrical signals in the brain, CS has been linked to important questions in neural decoding [8], [9], i.e., how the brain represents and transforms information. Understanding the dynamics of brain networks in the context of CS is a crucial aspect of this overall problem [8], [10]-[12]. Such networks are, of course, not static. Thus, recent interest has grown around so-called dynamic CS and, specifically, on the recovery of signals subjected to transformation via a dynamical system (or, network). In this context, sparsity has been formulated in three ways: 1) In the network states (state sparsity) [13]-[15]; 2) In the structure/parameters of the

- M. Kafashan and A. Nandi are with the Department of Electrical and Systems Engineering, Washington University in St. Louis, One Brookings Drive, Campus Box 1042, MO 63130, USA e-mail: kafashan@wustl.edu, nandia@ese.wustl.edu.
- S. Ching is with Faculty of Electrical Engineering &amp; the Division of Biology and Biomedical Sciences, Washington University in St. Louis, One Brookings Drive, Campus Box 1042, MO 63130, USA e-mail: shinung@ese.wustl.edu.

Fig. 1. Schematic of the considered network architecture. We study how the afferent, recurrent and output stages of this architecture interplay in order to enable accurate estimation of the input u t ( ) from y t ( ) in the presence of both disturbance and noise.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-9a28f9f7-b0a1-45b2-9bf6-fbd919c75f00.jpg)

network model (model sparsity) [16], [17]; and 3) In the inputs to the network (input sparsity) [18]-[28]. Here, we consider this latter category of recovery problems.

Our motivation is to understand how three stages of a generic network architecture - an afferent stage, a recurrent stage, and an output stage (see Fig. 1) - interplay in order to enable an observer, sampling the output, to recover the (sparse) input. Such an architecture is pervasive in sensory networks in the brain wherein a large number of sensory neurons, receiving excitation from the periphery, impinge on an early recurrent network layer that transforms the afferent excitation en route to higher brain regions [29], [30]. Moreover, beyond neural contexts, understanding network characteristics for dynamic CS may aid in the analysis of systems for efficient processing of naturally sparse time-varying signals [20]; and in the design of resilient cyber-physical systems [18], [19], [21], wherein extrinsic perturbations are sparse and time-varying. Toward these potential instantiations, our specific aim in this paper is to elucidate fundamental dynamical characteristics of linear networks for exact and stable recovery of the (sparse) input signal, corrupted by an input disturbance.

## B. Paper Contributions

To achieve our specific aim, we develop and present the following contributions:

- 1) We develop analytical conditions on the network dynamics, related to the classical notion of observability for a linear system, such that the network admits exact and stable (in the presence of output noise) input recovery.
- 2) We derive an upper bound in terms of the network dynamics, for the l 2 -norm of the reconstruction error over a finite time horizon. This error can be defined in terms of both the disturbance and the noise.
- 3) Based on the error analysis, we characterize a basic tradeoff between the ability of a network to simultaneously reject input disturbances while still admitting stable recovery.
- 4) We highlight network characteristics that optimally balance this tradeoff, and demonstrate via several examples their ability to reconstruct corrupted time-varying input from noisy observations. In particular, we highlight an example of a rate-based neuronal network, and how specific features of the network architecture mediate these tradeoffs.

## C. Prior Results in Sparse Input Recovery

The sparse input recovery problem for linear systems can be formulated in both the spatial and temporal dimension. Our contributions are related to the former. As mentioned above, in this context, previous work has considered recovery of spatially sparse inputs for network resilience [18], [19] and encoding of inputs with sparse increments [20]. In [21], conditions for exact sparse recovery are formulated in terms of a coherence-based observability criterion for intended applications in cyber-physical systems. Our contributions herein provide a general set of analytical results, including performance bounds, pertaining to exact and stable sparse input recovery of linear systems in the presence of both noise and disturbance.

A second significant line of research in sparse input recovery problems pertains to the temporal dimension. There, the goal is to understand how a temporally sparse signal (i.e., one that takes the value of zero over a nontrivial portion of its history) can be recovered from the state of the network at a particular instant in time. This problem forms the underpinning of a characterization of 'memory' in dynamical models of brain networks [22]-[27]. In particular, in [28] the problem of ascertaining memory is related to CS performed on the network states, over a receding horizon of a scalar-valued input signal. In contrast to these works, we consider spatial sparsity of vectorvalued inputs with explicit regard for both disturbance and an overt observation equation, i.e., states are not be directly sampled, but are transformed to an (in general lower-dimensional) output.

## D. Paper Outline

The remainder of the paper is organized as follows. In Section II we provide motivation of the current work and formulate the problem in detail. In Section III we develop theoretical results on the performance of the proposed recovery method. Simulation results for several different scenarios are provided in Section IV. Finally, conclusions are formulated in Section V.

## II. PROBLEM FORMULATION

We consider a discrete-time model for a linear network, formulated in the typical form a linear dynamical system, i.e.,:

$$r _ { k + 1 } & = \text{Ar} _ { k } + \text{Bu} _ { k } + \text{d} _$$

where k is an integer time index, r k ∈ R n is the activity of the network nodes (e.g., in the case of a rate-based neuronal network [31]-[37], the firing rate of each neuron), u k ∈ R m is the extrinsic input, d k ∈ R n is the input disturbance, e k ∈ R p is the measurement noise independent from d k , and y k ∈ R p is the observation at time k . The matrix A ∈ R n × n describes connections between nodes in the network, B ∈ R n × m contains weights between input and output and C ∈ R p × n is the measurement matrix. Such a model is, of course, quite general and can be used to describe recurrent dynamics in neuronal networks [38]-[42], machine learning applications such as pattern recognition and data mining [43]-[46], etc.

We consider the case of bounded disturbance and noise, i.e., ‖ e k ‖ /lscript 2 ≤ /epsilon1 , ‖ d k ‖ /lscript 2 ≤ /epsilon1 ′ . Since m , the number of input nodes, is larger than n , the number of output nodes, B takes the form of a 'wide' matrix. We assume that at each time at most s input nodes are active ( s -sparse input), leading to an /lscript 0 constraint to (1) at each time point:

$$\| \mathbf u _ { k } \| _ { \ell _ { 0 } } & \leq s. & \quad \quad \quad$$

In the absence of disturbance and noise, recovering the input of (1) with the /lscript 0 constraint (2) amounts to the optimization problem:

$$( P 0 ) \underset { ( r _ { k } ) ^ { K } _ { k = 0 } ( u _ { k } ) ^ { K -$$

It is clear that Problem ( P 0 ) is a non-convex discontinuous problem, which is not numerically feasible and is NP-Hard in general [47]. For static cases, such /lscript 0 optimization problems fall into the category of combinatorial optimization which require exhaustive search to find the solution [48].

Thus, throughout this paper, we follow the typical relaxation methodology used for such problems wherein the /lscript 0 norm is relaxed to the l 1 norm, resulting in the problem:

$$\text{u-1 month, rounding} & \text{$m$ and previous} \\ ( P 1 ) \quad & \minimize _ { ( r _$$

In the case that either input disturbance, or measurement noise, or both exist, we solve the following convex optimization Problem ( P 2 ):

$$( P 2 ) & \underset { ( r _ { k } ) ^ { K } _ { k = 0 } ( \mathbf u _ { k } ) ^ { K - 1 } _ { k = 0 } } { \minimize } \underset { k = 0 } { \sum _ { k = 0 } ^ { K - 1 } \| \mathbf u _ { k } \| _ { \ell _$$

where /epsilon1 ′′ is 2-norm of a surrogate parameter that aggregates the effects of disturbance and noise. In the case of noisy measurement with no disturbance /epsilon1 ′′ = /epsilon1 . In the next section, we show conditions for the network (1) under which Problems ( P 1 ) and ( P 2 ) result in exact and stable solutions.

## III. RESULTS

We will develop our results in several steps. First, we consider two cases for the observation matrix C in the absence of input disturbance, and proceed to establish existence and performance guarantees for solutions to the convex problems ( P 1 ) and ( P 2 ) for each case. After that, we continue the analysis to characterize the ability of a network to reject input disturbances while still admitting stable recovery in the presence of disturbance and noise, simultaneously.

## A. Preliminaries

We begin by recalling some basic matrix notation and matrix norm properties that will be used throughout this paper. Given normed spaces ( R n 1 , ‖ ‖ . /lscript 2 ) and ( R n 2 , ‖ ‖ . /lscript 2 ) , the corresponding induced norm or operator norm denoted by ‖ ‖ . i, 2 over linear maps D : R n 1 → R n 2 , D ∈ R n 2 × n 1 is defined by where σ ( M ) is the set of eigenvalues of M (or the spectrum of M ).

$$\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \$$

Definition 1 : A vector is said to be s -sparse if ‖ c ‖ /lscript 0 ≤ s , in other words it has at most s nonzero entries.

It is well known that in the static case (standard CS), exact and stable recovery of sparse inputs can be obtained under the restricted isometry property (RIP) [4]-[7], [49], defined as:

Definition 2 : The restricted isometry constant δ s of a matrix Φ ∈ R n × m is defined as the smallest number such that for all s -sparse vectors c ∈ R m the following equation holds

$$( 1 - \delta _ { s } ) \| c \| _ { \ell _ { 2 } } ^ { 2 } \leq \| \Phi c \| _ { \ell _ { 2 } } ^ { 2 } \leq ( 1 + \delta _ { s } ) \| c \| _ { \ell _ { 2 } } ^ { 2 }. \quad \quad \quad$$

It is known that many types of random matrices with independent and identically distributed entries or subGaussian matrices satisfy the RIP condition (7) with overwhelming probability [50]-[52].

## B. Case 1: Full-rank Square Observation Matrix C without Input Disturbance

In the first case, we consider (1) in the absence of input disturbance ( d k = 0 ) and we assume that the linear map C : R n → R n , p = n , has no nullspace, N ( C ) = { } 0 , which means that the network states can be exactly recovered by inverting the observation equation (1) (the trivial case being C equal to the identity). Our first result establishes a one to one correspondence between sparse input and observed output for the system (1).

Lemma 3 : Suppose that the sequence ( y k ) K k =0 from noiseless measurements is given, and A B C , , , N ( C ) = { } 0 are known. Assume the matrix B satisfies the RIP condition (7) with isometry constant δ 2 s &lt; 1 . Then, there is a unique s -sparse sequence of ( u k ) K -1 k =0 and a unique sequence of ( r k ) K k =0 that generate ( y k ) K k =0 .

Proof. See Appendix A.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-ba688dc3-fbef-4fdf-bce6-d7e09a63ca93.jpg)

Having established the existence of a unique solution, we now proceed to study convex Problems ( P 1 ) and ( P 2 ) that recover these solutions. First, we provide theoretical results for the stable recovery of the input where measurements are noisy i.e., ( P 2 ).

Theorem 4 : (Noisy recovery) Assume that the matrix B satisfies the RIP condition (7) with δ 2 s &lt; √ 2 -1 . Suppose that the sequence ( y k ) K k =0 is given and generated from sequences ( ¯ r k ) K k =0 and s -sparse ( ¯ u k ) K -1 k =0 based on

$$\bar { r } _ { k + 1 } & = A \bar { r } _ { k } + \mathbf B \bar { u } _ { k }, \ k = 0, \cdots, K - 1 \\ y _ { k } & = C \bar { r } _ { k } + e _ { k }, \ k = 0, \dots, K,$$

where ( ‖ e k ‖ /lscript 2 ≤ /epsilon1 ) K k =0 and A B C , , , N ( C ) = { } 0 are known. Then, the solution to Problem ( P 2 ) obeys where

$$\sum _ { k = 0 } ^ { K - 1 } \| \mathfrak { u } _ { k } ^ { * } - \bar { \mathfrak { u } } _ { k } \| _ { \ell _ { 2 } } \leq C _ { s } \epsilon,$$

$$C _ { s } = 2 \alpha C _ { 0 } K ( 1 - \rho ) ^ { - 1 }.$$

C , 0 ρ, α are given explicitly below:

$$n & \text{explicitly below} \colon \\ & C _ { 0 } = \frac { 1 } { \sqrt { \sigma } } \left ( 1 + \sqrt { \frac { \sigma _ { \max } \left ( C ^ { T } C \right ) \sigma _ { \max } \left ( A ^ { T } A \right ) } { \sigma _ { \min } \left ( C ^ { T } C \right ) } } \right ), \\ & \alpha = \frac { 2 \sqrt { 1 + \delta _ { 2 s } } } { 1 - \delta _ { 2 s } }, \\ & \rho = \frac { \sqrt { 2 } \delta _ { 2 s } } { 1 - \delta _ { 2 s } }, \\ & \sigma _ { \min } \left ( C ^ { T } C \right ) < \sigma < \sigma _ { \max } \left ( C ^ { T } C \right ). \\ & \text{at the the sequences} \left ( \mathfrak { r } _ { k } ^ { * } \right ) _ { k = 0 } ^ { K } \text{ and sparse} \left ( \mathfrak { u } _ { k } ^ { * } \right ) _ { k = 0 } ^ { K - 1 } \text{ are the solutions of Problem} \left ( P ^ { 2 } \right ). \text{ First we} \right ) \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{                                                                                                                                                                                                        
                                                                                                                                                                                                        }                                                                                                                                                                                                        \text{                                                                                                                                                                                                    
   & \text{or the $\|\mathfrak{r}_{k}_{k}_{\mathfrak{e2}$ in the following Lemma.} } \text{                                                                                                                                                                                                    \text{  }                                                                                                                                                                                                      \text                                                                                                                                                                                                       	                                                                                                                                                                                                        :                                                                                                                                                                                                       .                                                                                                                                                                                                        -                                                                                                                                                                                                        "                                                                                                                                                                                                       '                                                                                                                                                                                                       <                                                                                                                                                                                                        +                                                                                                                                                                                                        |$$

Lemma 5 : Suppose that the sequence ( y k ) K k =0 is given and generated from sequences ( ¯ r k ) K k =0 and s -sparse ( ¯ u k ) K -1 k =0 based on (8), where ( ‖ e k ‖ /lscript 2 ≤ /epsilon1 ) K k =0 and A B C , , , N ( C ) = { } 0 are known. Then, any solution r ∗ k to Problem ( P 2 ) obeys

Proof. Assume that the the sequences ( r ∗ k ) K k =0 and sparse ( u ∗ k ) K -1 k =0 are the solutions of Problem ( P 2 ). First we derive the bound for the ‖ r ∗ k -¯ r k ‖ /lscript 2 in the following Lemma.

$$\| \mathbf r _ { k } ^ { * } - \bar { \mathbf r } _ { k } \| _ { \ell _ { 2 } } & \leq \frac { 2 \epsilon } { \sqrt { \sigma _ { \min } \left ( \mathbb { C } ^ { T } \mathbb { C } \right ) } }$$

## Proof. See Appendix B

From Lemma 5, non-singularity of C and the equation y k = CA¯ r k -1 + CB¯ u k -1 + e k we can derive a bound for ‖ B u ( ∗ k -¯ u k ) ‖ /lscript 2 as

$$\text{a 5, non-singularity of $C$ and the equation $y_{k}=CA\bar{r}_{k-1}+CB\bar{u}_{k-1}+e_{k}$ we can derive a bound} \\ \text{i} _ { k } \left \| _ { \ell _ { 2 } } \text{ as} \\ \sqrt { \sigma } \right \| B \left ( \text{u} _ { k } ^ { * } - \bar { \mathbf u } _ { k } \right ) \left \| _ { \ell _ { 2 } } = \left \| C B \left ( \text{u} _ { k } ^ { * } - \bar { \mathbf u } _ { k } \right ) \right \| _ { \ell _ { 2 } } \\ & = \left \| ( \text{e} _ { k + 1 } ^ { * } + \text{e} _ { k + 1 } ) + C \text{A} ( \bar { r } _ { k } - \text{r} _ { k } ^ { * } ) \right \| _ { \ell _ { 2 } } \\ & \leq \left \| \text{e} _ { k + 1 } + \text{e} _ { k + 1 } ^ { * } \right \| _ { \ell _ { 2 } } + \left \| C \text{A} ( \bar { r } _ { k } - \text{r} _ { k } ^ { * } ) \right \| _ { \ell _ { 2 } } \\ & \leq 2 \epsilon \left ( 1 + \sqrt { \frac { \sigma _ { m a x } \left ( C ^ { T } C \right ) \sigma _ { m a x } \left ( A ^ { T } A \right ) } { \sigma _ { m i n } \left ( C ^ { T } C \right ) } } \right ),$$

which results in

$$\| \mathbf B \left ( \mathbf u _ { k } ^ { * } - \bar { \mathbf u } _ { k } \right ) \| _ { \ell _ { 2 } } \leq 2 C _ { 0 } \epsilon. \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ ( 1 4 ) \\. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

Now, denote u ∗ k = ¯ u k + h k where h k can be decomposed into a sum of vectors h k,T 0 ( k ) , h k,T 1 ( k ) , h k,T 2 ( k ) , · · · for each k , each of sparsity at most s . Here, T 0 ( k ) corresponds to the location of non-zero elements of ¯ u k , T 1 ( k ) to the location of s largest coefficients of h k,T c 0 ( k ) , T 2 ( k ) to the location of the next s largest coefficients of h k,T c 0 ( k ) ,

and so on. Also, let T 01 ( k ) ≡ T 0 ( k ) ∪ T 1 ( k ) . Extending the technique in [7], [49], it is possible to obtain a cone constraint for the input in the linear dynamical systems.

Lemma 6 : (Cone constraint) The optimal solution for the input in Problem ( P 2 ) satisfies

$$\sum _ { k = 0 } ^ { K - 1 } \| \mathbf h _ {$$

Proof. See Appendix C.

We can further establish a bound for the right hand side of (15):

Lemma 7 : The optimal solution for the input in Problem ( P 2 ) satisfies the following constraint

$$\sum _ { k = 0 } ^ { K - 1 } \| \mathbf h _ {$$

Proof. See Appendix D.

Finally, based on Lemma 6 and Lemma 7, it is easy to see that

$$\ n L e m a { 6 } & \text{ and Lemma 7, it is easy to$$

We now state a Theorem that characterizes the solution for the noiseless case (P1), which follows as a special case of (P2) as the noise variance approaches zero.

Theorem 8 : (Noiseless recovery) Assume that the matrix B satisfies the RIP condition (7) with δ 2 s &lt; √ 2 -1 . Suppose that the sequence ( y k ) K k =0 is given and generated from sequences ( ¯ r k ) K k =0 and s -sparse input ( ¯ u k ) K -1 k =0 based on dynamical equation (1), and A B C , , , N ( C ) = { } 0 are known. Then the sequences ( ¯ r k ) K k =0 and ( ¯ u k ) K -1 k =0 are the unique minimizer to Problem ( P 1 ).

Proof. It is sufficient to consider /epsilon1 = 0 in equation (49) which results in ‖ h 0 ,T 01 (1) ‖ /lscript 2 = · · · = ‖ h K -1 ,T 01 ( K -1) ‖ /lscript 2 = 0 from equation (54), which implies that all elements of vectors h 0 , · · · , h K -1 are zero and ( u ∗ k = ¯ u k ) K -1 k =0 .

## C. Case 2: Observation Matrix C Satisfying Observability Condition without Input Disturbance

In this case, we consider (1) in the absence of input disturbance ( d k = 0 ) with the linear map C : R n → R p , p &lt; n . Thus, direct inversion of C is not possible in this case. For any positive K , we define the standard linear observability matrix as

$$\mathcal { O } _ { K } \equiv \begin{pmatrix} C$$

If rank ( O K ) = n , then the system (1) is observable in the classical sense 1 . However, we do not assume any knowledge of the input other than the fact that it is s -sparse at each time. Note that if we simply iterate the output

1 The system is said to be observable if, for any initial state and for any known sequence of input there is a positive integer K such that the initial state can be recovered from the outputs y 0 , y 1 ,..., y K .

s

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-56449ed6-510a-41fd-b457-0b1a67654883.jpg)

s

Fig. 2. The matrix B s k is the n × s matrix corresponding the active columns of the full matrix B at time step k .

equation in (1) for K +1 time steps and exploit the fact that the input vector is s -sparse as shown in Fig. 2, we obtain:

where J s K is as follows:

$$\begin{array} {$$

$$\mathcal { J } _ { K } ^ { s } = \begin{pmatrix} 0 & 0 & \cdots & 0 \\ \mathcal { C } B _ { 0 } ^ { s } & 0 & \cdots & 0 \\ \mathcal { C } A B _ { 0 } ^ { s } & \mathcal { C } B _ { 1 } ^ { s } & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ \mathcal { C } A ^ { K - 1 } B _ { 0 } ^ { s } & \mathcal { C } A ^ { K - 2 } B _ { 1 } ^ { s } & \cdots & \mathcal { C } B _ { K - 1 } ^ { s } \end{pmatrix}, \quad ( 2 0 )$$

( ) In the next Theorem, we establish conditions under which a one to one correspondence exists between sparse input and observed output for the system (1).

where B s i is the n × s matrix corresponding the active columns of B (corresponding to nonzero input entries) at time step i (see Fig. 2). In general, we do not know where active columns of B are located at each time a priori . We define J s K as the set of all possible matrices satisfying the structure in (20), where the cardinality of this set is m K s .

Lemma 9 : Suppose that the sequence ( y k ) K k =0 from noiseless measurements is given, and A B , and C are known. Assume rank ( O K ) = n and the matrix CB satisfies the RIP condition (7) with isometry constant δ 2 s &lt; 1 . Further, assume

$$\ r a n k ( [ \mathcal { O } _ { K } & \mathcal { J } _ { K } ^ { 2 s } ] ) = n + r a n k ( \mathcal { J } _ { K } ^ { 2 s } ), \ \forall \mathcal { J } _ { K } ^ { 2 s } \in \mathbf J _ { K } ^ { 2 s }. \\. & \quad. \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cd� \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cd: \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cd.. \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cd> \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdents \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdocks \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots \ \cd><> \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \end{cases}$$

Then, there is a unique s -sparse sequence of ( u k ) K -1 k =0 and a unique sequence of ( r k ) K k =0 that generate ( y k ) K k =0 .

Proof. See Appendix E.

Remark 10 : The rank condition implies that all columns of the observability matrix must be linearly independent of each other (i.e., the network is observable in the classical sense) and of all columns of J s K . Since the exact location of the nonzero elements of the input vector are not known a priori , this condition is specified over all J 2 s K . Thus, (21) is a combinatorial condition. From our simulation studies, we observe that this condition holds for random Gaussian matrices almost always and, moreover, can be numerically verified for certain salient random networks (see also Example 3 in Section IV).

Having established the existence of a unique solution, we now proceed to study the convex problems ( P 1 ) and ( P 2 ) that recover these solutions for this case. First, we provide theoretical results for the stable recovery of the input where measurements are noisy i.e., (P2).

Theorem 11 : (Noisy recovery) Assume rank ( O K ) = n and the matrix CB satisfies the RIP condition (7) with δ 2 s &lt; √ 2 -1 . assume (21) holds. Suppose that the sequence ( y k ) K k =0 is given and generated from sequences ( ¯ r k ) K k =0 and s -sparse ( ¯ u k ) K -1 k =0 based on (8), where ( ‖ e k ‖ /lscript 2 ≤ /epsilon1 ) K k =0 and A B , and C are known. Then, any s -sparse solution of Problem ( P 2 ) obeys

$$\exists \, C _ { s } \ s u c h \ t h a t \, \sum _ { k = 0 } ^ { K - 1 } \| \mathfrak { u } _ { k } ^ { * } - \bar { \mathfrak { u } } _ { k } \| _ { \ell _ { 2 } } \leq C _ { s } \epsilon.$$

Proof. See Appendix F.

Theorem 12 : (Noiseless recovery) Assume rank ( O K ) = n and the matrix CB satisfies the RIP condition (7) with δ 2 s &lt; √ 2 -1 . Further, assume (21) holds. Suppose that the sequence ( y k ) K k =0 is given and generated from sequences ( ¯ r k ) K k =0 and s -sparse inputs ( ¯ u k ) K -1 k =0 based on dynamical equation (8), where /epsilon1 = 0 and A B , and C are known. Then the sequences ( ¯ r k ) K k =0 and ( ¯ u k ) K -1 k =0 are the unique minimizer to Problem ( P 1 ).

Proof. It can be concluded from Lemma 9 and Theorem 11 that with the assumption stated in the theorem and /epsilon1 = 0 the sequences ( ¯ r k ) K k =0 and ( ¯ u k ) K -1 k =0 are the unique minimizer to Problem ( P 1 ).

Remark 13 : Imposing an RIP condition on the combined matrix CB bears some conceptual similarity to the formulation of an overcomplete dictionary in the classical compressed sensing literature [53], [54]. In this sense, the B matrix (i.e., the afferent stage) can be interpreted as a dictionary that transforms the sparse input u onto the recurrent network states.

## D. Case 3: Optimal Network Design to Enable Recovery in the Presence of Disturbance and Noise

Finally, we show how eigenstructure of the network implies a fundamental tradeoff between stable recovery and rejection of disturbance (i.e., corruption).

It is easy to see from (9) that the upper-bound of the recovery error is reduced by decreasing the maximum singular value of A . Thus, from now on we use the upper-bound of the input recovery error as a comparative measure of performance. In the absence of both disturbance and noise, the best error performance is achieved when A = 0 , i.e., the network is static, which in intuitive since in this scenario any temporal effects would smear the salient parts of the signal.

On the other hand, having dynamics in the network should improve the error performance in the presence of the disturbance. To demonstrate this, consider (1) with d k nonzero. When A = 0 , i.e., a static network, the disturbance can be exactly transformed to the measurement equation resulting in Cd k + e k as a surrogate measurement noise with

In this case, the error upper-bound can be obtained by exploiting the result of Theorem 4 as

$$\text{$a$ to the measurement equation resulting in $\mathcal{Co}_{k}+e_{k}$ as a surrogate measurement noise} \\ & \| \text{Cd}_{k}+e_{k} \| _ { \ell _ { 2 } } \leq \sqrt { \sigma ^ { \prime } \epsilon ^ { \prime } + \epsilon, } \\ & \sigma _ { \min } \left ( \text{C} ^ { T } \text{C} \right ) < \sigma ^ { \prime } < \sigma _ { \max } \left ( \text{C} ^ { T } \text{C} \right ). } \\ \text{er-bound can be obtained by exploiting the result of Theorem $4$ as} \\ & K = 1$$

$$\sum _ { k = 0 } ^ { K - 1 } & \| u _ { k } ^ { * } - \bar { u } _ { k } \| _ { \ell _ { 2 } } \leq C _ { s } ^ { \prime } ( \sqrt { \sigma ^ { \prime } } \epsilon ^ { \prime } + \epsilon ), \\ C _ { s } ^ { \prime } & = \frac { 2 } { \sqrt { \sigma } } \alpha K ( 1 - \rho ) ^ { - 1 }. \\ \text{is not accessible to another man that determine to the output as shown.                                                                                                                                                                                                         }$$

When A is nonzero, it is not possible to exactly map the disturbance to the output as above. Nevertheless, it is straightforward to approximate the relative improvement in performance. For instance, consider a system with A symmetric and where the disturbance and input are in displaced frequency bands. Then it is a direct consequence of linear filtering that the power spectral density of the disturbance can be attenuated according to

$$\mathcal { S } _ { \text{d} } \text{fin} ( e ^$$

Fig. 3. The recovered input for (A) p = n (B) p = 35 for both static (middle images) and dynamic (left images) CS where n = 45 and m = 68 . Original input is in the right hand side denoted as true digit.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-7d1939ac-7ed7-4363-89c0-3a3d68838f04.jpg)

where ω is the frequency of the disturbance. So, for instance, if ω = π ,

$$\text{s.s.s.s.s.s.s.s.s.s$$

where λ i ( A ) is the i th eigenvalue of matrix A . Assuming the input is sufficiently displaced in frequency from the disturbance, the error upper-bound can be then readily approximated using the results of Theorem 4 as follows

$$\text{e error upper-bound can be then readily approximated using the results of Theorem 4 as$$

By comparing (24) and (27), it is easy to verify that A and C can be designed in a way to reduce error upper-bound at least by a factor of two, assuming σ ′ and σ ′′ are close to each other. In the examples below, we will show that, in fact, performance in many cases can exceed this bound considerably.

## IV. EXAMPLES

In this section, we present several examples that demonstrate the developed results. For solving our convex optimization problems, we used CVX with MATLAB interface [55], [56]. To create example networks, we generated the matrices A B C , , using a Gaussian random number generator in MATLAB.

## A. Example 1: One-step and Sequential Recovery

In this experiment, we consider a dynamical system with sparse input which satisfies conditions in Theorem 11. Here, we consider random Gaussian matrices for A B , and C , with n = 45 , m = 68 . The input is defined as the image of a digit, shown in Fig. 3 with values between 0 and 1, where the horizontal axis is treated as time, i.e., column k of the image is the input to the system at time k .

We proceed to perform input recovery in two ways: (i) by solving ( P 1 ) in one step over the entire horizon K , i.e., one-step recovery; and (ii) by solving ( P 1 ) K times, sequentially, i.e., recovery at each time step. We compare the outcomes for two cases:

a) Full Rank C : Fig. 3A shows the recovered input for the case that p = n for both one-step and sequential recovery, and it can be seen that sparse input can be recovered in two cases perfectly. This is expected, since in this case, C can be inverted at each time step.

Fig. 4. (A) MSE versus the maximum singular value of A , for several random realization of A with noise and in the absence of disturbance. (B) MSE versus the maximum singular value of A , for several random diagonal A with noise and disturbance.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-8bcb8b4b-833b-4e2d-adb0-18bd1e549cb3.jpg)

Fig. 5. MSE as a function of (A) log (1 //epsilon1 ) and (B) log (1 //epsilon1 ′ ) for the reconstructed input with n = 50 , m = 100 over 100 random trials (different random matrices A B C , , in each trial).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-ce62dfc5-41be-476f-b85e-439211c66c37.jpg)

b) C Satisfying Observability Condition: Fig. 3B of the figure illustrates the results for the case that p = 35 , but where C satisfies the observability condition. It is clear that sequential dynamic CS can not recover the input exactly. However, from our results (Theorem 12) we expect that one-step recovery (over the entire horizon) is possible, as is evidenced in the figure.

## B. Example 2: Recovery in the Presence of Disturbance and Noise

Fig. 4A shows the mean square error ( MSE ) versus the maximum singular value of A , for several random realization of A , in the case of full rank C . In this study, e k is assumed to follow an uniform distribution U -( 0 5 . , 0 5) . while d k = 0 . It can be seen from this figure that by increasing √ σ max ( A A T ) , the recovery performance is degraded, as we expect based on the derived bound for the error in (9).

We conducted simulation experiments to examine the effect of the noise and disturbance strength on the reconstruction error. Fig. 5 shows the average MSE for the reconstructed input versus log (1 //epsilon1 ) and log (1 //epsilon1 ′ ) , respectively with n = 50 , m = 100 for 100 random trials (different random matrices A, B, C in each trial). This figure shows that the reconstruction error decreases as a function of noise energy.

To contrast Fig. 4A, we consider the case when disturbance is added to the input. In Fig. 4B, we show the MSE versus √ σ max ( A A T ) for several random diagonal matrices A when e k ∼ U -( 0 5 . , 0 5) . and d k ∼ N (0 1) , . As expected from our results, √ σ max ( A A T ) can not be arbitrary small, since in this case the disturbance would entirely corrupt the input.

The next study illustrates recovery in the presence of both disturbance and noise for a smoothly changing sequence of 64 images (frames). Each frame, is corrupted with disturbance and at each time, and the difference between two consecutive frames is considered as the sparse input to the network. The disturbance d k is assumed to be a random variable drown from a Gaussian distribution, N (0 0 2) , . , passed through a fifth-order Chebyshev high pass

Fig. 6. (A) Four noiseless frames of a movie. Recovery via (B) static CS and (C) dynamic CS in the presence of disturbance.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-0053bbe6-014f-4158-bed8-b1df43f23793.jpg)

Fig. 7. PSNR of the recovered frame versus frame number for both CS with and without dynamics.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-dfb3e971-835f-4b22-8510-f9296f7d49a6.jpg)

filter. Each frame has m = 400 pixels and K = 64 . Furthermore, we consider random Gaussian matrices for B and C with n = p = 200 .

We proceeded to design the matrix A to balance the performance bound (9) and the ability to reject the disturbance as per Section III-D. Fig. 6A shows the original frames at different times. We assumed the first frame is known exactly. Frames recovered from the output of a static network , i.e., A = 0 are depicted in Fig. 6B. In contrast, frames recovered from the output of the designed dynamic network are shown in Fig. 6C. It is clear from the figure that quality of recovery is better in the latter case. Fig. 7 illustrates the PSNR, defined as 10log( 1 MSE ) as a function of frame number with and without dynamics. It can be concluded from this figure that having a designed matrix A results in recovery that is more robust to disturbance, while without dynamics, error propagates over time, and the reconstruction quality is degraded.

## C. Example 3: Input Recovery in an Overactuated Rate-Based Neuronal Network

A fundamental question in theoretical neuroscience centers on how the architecture of brain networks enables the encoding/decoding of sensory information [10], [57]. In our final example, we use the results of Theorems 4 and 12 to highlight how certain structural and dynamical features of neuronal networks may provide the substrate for sparse input decoding.

Fig. 8. (A) The maximum singular value of A versus the inhibition percentage. MSE of input recovery in the presence of (B) Noise and (C) Disturbance as a function of the percent of inhibitory neurons.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-06ed87b1-ce62-4868-bf18-603dd44fc5c4.jpg)

Specifically, we consider a firing rate-based neuronal network [34] of the form

$$\mathbf T _ { r } \frac { d r } { d t } = - r +$$

with input rates u ∈ R m , output rates r ∈ R n , a feed-forward synaptic weight matrix W ∈ R n × m , and a recurrent synaptic weight matrix M ∈ R n × n . We consider n = 50 neurons which receive synaptic inputs from m = 100 afferent neurons, i.e., neurons that impinge on the network in question. Here, T r ∈ S n + is a diagonal matrix whose diagonal elements are the time constants of the neurons. A discrete version of (28), alongside a linear measurement equation can be written in the standard form (1) where A = I n -∆ t T r -1 +∆ t T r -1 M is related to connections between nodes in the network, and B = ∆ t T r -1 W contains weights between input and output nodes. For this example, we assume that the network connectivity has a Watts-Strogatz small-world topology [58] with connection probability p M and rewiring probability q M .

The recurrent synaptic matrix M is defined as

$$\begin{array} {$$

 For the purposes of illustration, we select the diagonal elements of matrix T r , from a uniform distribution U (0 1 . , 0 2) . . We study the recovery performance associated with the network over 100 time steps, assuming a timescale of milliseconds and an discretization step of 0 1 . ms . At each time step, the nonzero elements of the input vector u , i.e., firing rate of the afferent neurons, are drawn from an uniform distribution U (0 5 . , 1 5) . . Moreover, we assume that elements of the observation matrix C are drawn from a Gaussian distribution N (0 1) , . Finally, we assume m E ij and m I ij are drawn from lognormal distributions ln N (0 1) , and ln N (0 0 1) , . , respectively. The latter assumption is chosen for illustration only and is not related to known physiology.

1) Recovery Performance from Error Bounds: We proceed to conduct a Monte Carlo simulation of 100 different realizations of W M , and C . Fig. 8A illustrates that the maximum singular value of the matrix A decreases as a function of the percent of inhibitory neurons. Thus, we anticipate from our derived performance bounds that performance in terms of mean square error (MSE) should be best for networks with high inhibition in the presence of noise. This prediction bears out in Fig. 8B, where we indeed observe a monotone relationship between MSE

Fig. 9. (A) Examining the rank condition (21) in the networks of Example 3, with p = 30 , for different values of s . (B) The probability of exact recovery of dynamic sparse input to the network over s .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-23e2585a-354c-4c77-b514-5f66d2c78d39.jpg)

and inhibition. On the one hand, low-inhibition is favorable for facilitating recovery in the presence of disturbance depicted in Fig. 8C. Such tradeoffs are interesting to contemplate when considering the functional advantages of network architectures observed in biology, such as the pervasive 80-20 ratio of excitatory to inhibitory neurons [34], [59]. Together, Figs. 8B and 8C illustrate how the excitatory-inhibitory ratio mediate a basic tradeoff in the capabilities of a rate-based neuronal network.

2) Recoverable Sparsity based on Theorem 12: Having ascertained the performance tradeoff curves, we sought to characterize in more detail the level of recoverable sparsity with specific connection to Theorem 12 and (21). We considered networks as above, but with p = 30 and 20/80 for the ratio of inhibitory/excitatory over 10 time steps for 100 random trials. Thus, the output of the network is of lower dimension than the network state space and the observability matrix is of nontrivial construction. Fig. 9A shows that for this setup, the rank condition (21) holds up to 2 s = 27 . Thus, Theorem 12 predicts that recover will be possible (to within the RIP condition on CB ) for signals with 13 nonzero elements. Fig. 9B validates this theoretical prediction by illustrating recovery performance in the absence of disturbance and noise for different values s . It is observed that when the rank condition holds, reconstruction is perfect and that the probability of exact recovery is decreased by increasing s , as expected.

## V. CONCLUSION

## A. Summary

In this paper, we present several results pertaining to the effect of temporal dynamics on compressed sensing of time-varying signals. Specifically, we considered the recovery of sparse inputs to a linear dynamical system (network) from limited observation of the network states. We provide basic conditions on the system that ensure solution existence and, further, derive several bounds in terms of the system dynamics for recovery performance in the presence of both input disturbance and observation noise. We show that dynamics can play opposing roles in mediating accurate recovery with respect to these two different sources of corruption. Thus, our results indicate tradeoffs that may inform the design of dynamical systems for time-varying compressed sensing. These tradeoffs are illustrated through a series of examples, including one that highlights how the developed theory could be used to interrogate the functional role of inhibition in a neuronal network.

## B. Implications and Future Work

The results can have both engineering and scientific impacts. In the former case, the goal may be to design networks to process time-varying signals that are naturally sparse, such as high-dimensional neural data, or to be resilient to time-varying sparse perturbations. In the latter case, the goal is to understand how the naturally occurring architectures of networks, such as those in the brain, confer advantages for processing of afferent signals. In both cases, a precursor to further study are a set of verifiable conditions that overtly link network characteristics/dynamics to sparse input processing. Our paper provides such conditions for networks with linear dynamics and develops illustrative examples that highlight these potential applications. Treatment of systems with nonlinear dynamics, as well as a more detailed examination of random networks using the theory, are left as subjects for future work.

## APPENDIX A

## PROOF OF LEMMA 3

Based on the assumption on the null space of the linear map C : R n → R n , given ( y k ) K k =0 , there is a unique sequence of ( r k ) K k =0 . We now prove the uniqueness of ( u k ) K -1 k =0 . First, consider the following equations:

$$\begin{array} {$$

$$y _ { K } = C \text{Ar} _ { K - 1 } + \text{$$

The remainder of the proof is by contradiction. Let us assume that the sequence ( u k ) K -1 k =0 is not unique and there is another sequence of s -sparse ( ˆ u k ) K -1 k =0 which satisfies (30), leading to

$$\begin{array} { c } y _ { 0 } = C r _ { 0 } \\ y$$

$$\begin{smallmatrix} \\ \vdots \\ \end{smallmatrix}$$

$$y _ { K } = \text{CAr} _ { K - 1 } + \text{$$

Therefore, based on (30) and (31) we can conclude that

$$\begin{array} {$$

Matrix C is non-singular, hence equation (33) can be simplified as follows:

$$B ( u _ { 0 } - \hat { u } _ { 0 } ) = \dots$$

Based on the assumption that the matrix B satisfies the RIP condition (7) with isometry constant δ 2 s &lt; 1 and the fact that the support of the vectors ( u 0 -ˆ u 0 ) , · · · , ( u K -1 -ˆ u K -1 ) are at most 2 s , the lower bound of the RIP condition for B results in

$$\ n \, \text{for $B$ results in} \\ ( 1 - \delta _$$

which means that u 0 = ˆ u 0 , · · · , u K -1 = ˆ u K -1 and the sequence of s -sparse vectors ( u k ) K -1 k =0 is unique.

## APPENDIX B PROOF OF LEMMA 5

If r ∗ k is the solution to Problem ( P 2 ), then y ∗ k = Cr ∗ k satisfies the inequality in ( P 2 ) which means that ‖ y k -y ∗ k ‖ /lscript 2 ≤ /epsilon1 which can be reformulated as

$$y _ { k } ^ { * } = y _ { k } + e _ { k } ^$$

By replacing y k from (8) in (35) we have which results in

$$C r _ { k } ^ { * } & = C \bar { r } _ { k }$$

$$\| \mathbf r _ { k } ^ { * } - \bar { \mathbf r } _ { k } \| _ { \ell _ { 2 } } = \| \mathbf C ^ { - 1 } \left ( \mathbf e _ { k } + \mathbf e _ { k } ^ { * } \right ) \| _ { \ell _ { 2 } }. \\ \intertext { a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a n d a } \| \left ( \mathbf r _ { k } ^ { * } - \bar { \mathbf r } _ { k } \right ) \| \right )$$

Finally, we can derive the error bound for the state error at each time by substituting (6) into (37) as

$$\text{an derive the error bound for the state error at each time by substituting (6) into (37) as } \| \mathfrak { r } _ { k } ^ { * } - \bar { \mathfrak { r } } _ { k } \| _ { \ell _ { 2 } } & \leq \sqrt { \sigma _ { m a x } \left ( C ^ { - T } C ^ { - 1 } \right ) } \ \| e _ { k } + e _ { k } ^ { * } \| _ { \ell _ { 2 } } \\ & \leq \sqrt { \sigma _ { m a x } \left ( C ^ { - T } C ^ { - 1 } \right ) } \ \left ( \| e _ { k } \| _ { \ell _ { 2 } } + \| e _ { k } ^ { * } \| _ { \ell _ { 2 } } \right ) & & & ( 3 8 ) \\ & = \frac { 2 \epsilon } { \sqrt { \sigma _ { m i n } \left ( C ^ { T } C \right ) } }$$

## APPENDIX C

## PROOF OF LEMMA 6

For each j ≥ 2 and k = 0 , · · · , K -1 we have

$$\| \mathbf h _ { k, T _ { j } ( k ) } \| _ { \ell _ { 2 } } & \leq s ^ { 1 / 2 } \| \mathbf h _ { k, T _ { j } ( k ) } \| _ { l _ { \infty } } \leq s ^ { - 1 / 2 } \| \mathbf h _ { k, T _ { j - 1 } ( k ) } \| _ { \ell _ { 1 } },$$

and thus

$$\sum _ { j \geq 2 } \| \mathfrak { h } _ { k, T _ { j } ( k ) } \| _ { \ell _ { 2 } } & \leq s ^ { - 1 / 2 } ( \| \mathfrak { h } _ { k, T _ { 1 } ( k ) } \| _ { \ell _ { 1 } } + \| \mathfrak { h } _ { k, T _ { 2 } ( k ) } \| _ { \ell _ { 1 } } + \cdots ) \\ & \leq s ^ { - 1 / 2 } \| \mathfrak { h } _ { k, T _ { 2 } ^ { \zeta } ( k ) } \| _ { \ell _ { 1 } }. \\ \intertext { e have the following equation}$$

Therefore, we have the following equation

$$\lambda \ \cdot \ \cdot \\ \| \mathbf h _ { k, T _ { 0 } ^ { \sigma } ( k ) } \| _ { \ell _ { 2 } } & = \| \sum _ { j \geq 2 } \mathbf h _ { k, T _ { j } ( k ) } \| _ { \ell _ { 2 } } \leq \sum _ { j \geq 2 } \| \mathbf h _ { k, T _ { j } ( k ) } \| _ { \ell _ { 2 } } \\ & \leq s ^ { - 1 / 2 } \| \mathbf h _ { k, T _ { 0 } ^ { \sigma } ( k ) } \| _ { \ell _ { 1 } }. \\ \minimize \text{$thecostfunction in Problam $LDP$} \/$$

Since ( u ∗ k ) K -1 k =0 minimizes the cost function in Problem ( P 2 ),

$$\sum _ { k = 0 } ^ { K - 1 } \| \bar { u } _ { k } \| _ { \ell _ { 1 } } & \geq \sum _ { k = 0 } ^ { K - 1 } \| \bar { u } _ { k } ^ { * } \| _ { \ell _ { 1 } } = \sum _ { k = 0 } ^ { K - 1 } \| \bar { u } _ { k } + \bar { h } _ { k } \| _ { \ell _ { 1 } } \\ & = \sum _ { k = 0 } ^ { K - 1 } \left ( \sum _ { i \in T _ { 0 } ( k ) } | \bar { u } _ { k, i } + \sum _ { i \in T _ { 0 } ^ { * } ( k ) } | \bar { u } _ { k, i } + \bar { h } _ { k, i } | \right ) \\ & \geq \sum _ { k = 0 } ^ { K - 1 } ( \| \bar { u } _ { k, T _ { 0 } ( k ) } \| _ { \ell _ { 1 } } - \| \bar { h } _ { k, T _ { 0 } ( k ) } \| _ { \ell _ { 1 } } + \| \bar { h } _ { k, T _ { 0 } ^ { * } ( k ) } \| _ { \ell _ { 1 } } \\ & \quad + \| \bar { u } _ { k, T ^ { * } _ { 0 } ( k ) } \| _ { \ell _ { 1 } } ) \\ \dots \dots \dots \dots \epsilon \dots \epsilon \cap \tau \cap \tau \cap \tau \dots \dots \dots \epsilon \dots$$

k,T

+

‖

¯

u

c

0

(

k

)

‖

/lscript

1

)

¯ u 0 , · · · , ¯ u K -1 are non-zero for T 0 (0) , · · · , T 0 ( K -1) , respectively. Therefore,

$$\| \bar { \mathbf u } _ { 0, T _ { 0 } ^ { c } ( 0 ) } \| _ { \ell _ { 1 } } = \dots = \| \bar { \mathbf u } _ { K - 1, T _ { 0 } ^ { c } ( K - 1 ) } \| _ { \ell _ { 1 } } = 0$$

which gives

Considering

$$\sum _ { k = 0 } ^ { K - 1 } \| h _ { k, T _ { 0 } ^ { c } ( k ) } \| _ { \ell _ { 1 } } \leq \sum _ { k = 0 } ^ { K - 1 } \| h _ { k, T _ { 0 } ( k ) } \| _ { \ell _ { 1 } }.$$

$$\| \mathbf h _ { k, T _ { 0 } ( k ) } \| _ { \ell _ { 1 } } & \leq s ^ { 1 / 2 } \| \mathbf h _ { k, T _ { 0 } ( k ) } \| _ { \ell _ { 2 } }, & & ( 4 5 ) \\. \dots &.$$

and substituting it into (41) and (44) we have

$$\sum _ { k = 0 } ^ { K - 1 } \| h _ { k, T _ { 0 } ^ { 2 } ( k ) } \| _ { \ell _ { 2 } } \leq \sum _ { k = 0 } ^ { K - 1 } \| h _ { k, T _ { 0 } ( k ) } \| _ { \ell _ { 2 } },$$

## APPENDIX D

PROOF OF LEMMA 7

To find the bound for ∑ K -1 k =0 ‖ h k,T 01 ( k ) ‖ /lscript 2 , we start with

$$\text{Bh} _ { k } & = \text{Bh} _ { k, T _ { 0 1 } ( k ) } + \sum _ { j \geq 2 } \text{Bh} _ { k, T _ { j } ( k ) },$$

which gives

$$\| \text{Bh} _ { k, T _ { 0 1 } ( k ) } \| _ { \ell _ { 2 } } ^ { 2 } & = \langle \text{Bh} _ { k, T _ { 0 1 } ( k ) }, \text{Bh} _ { k } \rangle \\ & \quad - \langle \text{Bh} _ { k, T _ { 0 1 } ( k ) }, \sum _ { j \geq 2 } \text{Bh} _ { k, T _ { j } ( k ) } \rangle.$$

From (14) and the RIP condition for B ,

$$| \langle \text{Bh} _ { k, T _ { 0 1 } ( k ) }, \text{Bh} _ { k } \rangle | & \leq \| \text{Bh} _ { k, T _ { 0 1 } ( k ) } \| _ { \ell _ { 2 } } \| \text{Bh} _ { k } \| _ { \ell _ { 2 } } \\ & \leq 2 \epsilon C _ { 0 } \sqrt { 1 + \delta _ { 2 s } } \| \text{h} _ { k, T _ { 0 1 } ( k ) } \| _ { \ell _ { 2 } }, \\ \text{plication of the parallelogram identity for disjoint subsets } T _ { 0 } ( k ) \text{ and } T _ { j } ( k ), j \geq 2 \text{ results in}$$

and, moreover, application of the parallelogram identity for disjoint subsets T 0 ( k ) and T j ( k , j ) ≥ 2 results in

$$| \langle \text{Bh} _ { k, T _ { 0 } ( k ) }, \text{Bh} _ { k, T _ { j } ( k ) } \rangle | \leq \delta _ { 2 s } \| \text{h} _ { k, T _ { 0 } ( k ) } \| _ { \ell _ { 2 } } \| \text{h} _ { k, T _ { j } ( k ) } \| _ { \ell _ { 2 } }. \\ \cdots \cdots \cdots \cdots \cdots$$

Inequality (50) holds for T 1 in place of T 0 . Since T 0 and T 1 are disjoint

$$\sin \pi _ { 1 } \Pi \cos \pi _ { 0 } \cdot \Pi \cos \pi _ { 0 } \sum \pi _ { 1 } \sum \max \pi _ { 0 } \\ \left \| \mathbf h _ { k, T _ { 0 } ( k ) } \right \| _ { \ell _ { 2 } } + \left \| \mathbf h _ { k, T _ { 1 } ( k ) } \right \| _ { \ell _ { 2 } } \leq \sqrt { 2 } \| \mathbf h _ { k, T _ { 0 1 } ( k ) } \| _ { \ell _ { 2 } },$$

which results in

$$\text{ts in} & ( 1 - \delta _ { 2 s } ) \| \$$

It follows from (40) and (52) that

$$\| \mathbf h _ { k, T _ { 0 1 } ( k ) } \|$$

Now, using (44) and (53) we can conclude that which means

$$\Lambda \, \text{and} \, ( 5 3 ) \, \text{$$

$$\sum _ { k = 0 } ^ { K - 1 } \| \mathbf h _ {$$

## APPENDIX E

## PROOF OF LEMMA 9

We start the proof using contradiction. Let us assume that the sequence of ( u k ) K -1 k =0 and ( r k ) K k =0 is not unique and there is another sequence of s -sparse ( ˆ u k ) K -1 k =0 and ( ˆ r k ) K k =0 which satisfies the system (1) with noiseless measurements. Note that u k -ˆ u k has at most 2 s nonzero elements. Similar to the depiction in Fig. 2, we can rewrite (19) based on 2 s columns of B corresponding to 2 s active non-zero elements of u k -ˆ u k as

$$\begin{array} {$$

$$\bigvee ^ { J \, N } / \bigvee _ { K - 1 } / \\ \binom { y _ { 0 } } { y _ { 1 } } & = \mathcal { O } _ { K } \hat { r } _ { 0 } + \mathcal { J } _ { K } ^ { 2 s } \begin{pmatrix} \hat { u } _ { 0 } ^ { 2 s } \\ \hat { u } _ { 1 } ^ { 2 s } \\ \vdots \\ \hat { u } _ { K - 1 } ^ { 2 s } \end{pmatrix}.$$

By subtracting the above equations from each other we have

$$\text{ove equations nom eam one} \, \text{me} \, \text{me} \, \text{have} \\ \mathcal { O } _ { K } ( r _ { 0 } - \hat { r } _ { 0 } ) + \mathcal { J } _ { K } ^ { 2 s } \begin{pmatrix} u _ { 0 } ^ { 2 s } - \hat { u } _ { 0 } ^ { 2 s } \\ u _ { 1 } ^ { 2 s } - \hat { u } _ { 1 } ^ { 2 s } \\ \vdots \\ u _ { K - 1 } ^ { 2 s } - \hat { u } _ { K - 1 } ^ { 2 s } \end{pmatrix} = 0. \quad & ( 5 8 ) \\ \text{is that rank} ( \mathcal { O } _ { K } ) = n \, \text{ and rank} ( [ \mathcal { O } _ { K } - \mathcal { J } _ { K } ^ { 2 s } ] ) = n + \text{rank} ( \mathcal { J } _ { K } ^ { 2 s } ), \, \forall \mathcal { J } _ { K } ^ { 2 s } \in \mathcal { J } _ { K } ^ { 2 s }, \, \text{all columns of} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \,  \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{ne} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \, \text{me} \,$$

Based on assumptions that rank ( O K ) = n and rank ([ O K J 2 s K ]) = n + rank ( J 2 s K ) , ∀J 2 s K ∈ J 2 s K s , all columns of the observability matrix must be linearly independent of each other, and of all columns of the J 2 K matrix. Hence, the vector r 0 -ˆ r 0 = 0 . Having r 0 = ˆ r 0 and the matrix CB satisfying the RIP condition (7) with isometry constant δ 2 s &lt; 1 , it is easy to see that u k = ˆ u k and therefore there exists unique state and s -sparse input sequences.

## APPENDIX F

## PROOF OF THEOREM 11

Lets assume that the the sequences ( r ∗ k ) K k =0 and s -sparse ( u ∗ k ) K -1 k =0 are the solutions of Problem ( P 2 ). In this case (58) can be rewritten as

$$\mathcal { O } _ { K } ( r _ { 0 } ^ { * } - \bar { r } _ { 0 } ) + \mathcal { J } _ { K } ^ { 2 s } \begin{pmatrix} u _ { 0 } ^ { * 2 s } - \bar { u } _ { 0 } ^ { 2 s } \\ u _ { 1 } ^ { * 2 s } - \bar { u } _ { 1 } ^ { 2 s } \\ \vdots \\ u _ { K - 1 } ^ { * 2 s } - \bar { u } _ { K - 1 } ^ { 2 s } \end{pmatrix} = \begin{pmatrix} e _ { 0 } \\ e _ { 1 } \\ \vdots \\ e _ { K } \end{pmatrix} + \begin{pmatrix} e _ { 0 } ^ { * } \\ e _ { 1 } ^ { * } \\ \vdots \\ e _ { K } ^ { * } \end{pmatrix}, \\ \| _ { \mathcal { L } _ { 2 } } \leq \epsilon. \ B a s e d o n a s u m p t i o n s t a r a n k ( \mathcal { O } _ { K } ) = n \, \text{and} \, \text{rank} ( [ \mathcal { O } _ { K } \, \mathcal { J } _ { K } ^ { 2 s } ] ) = n + \text{rank} ( \mathcal { J } _ { K } ^ { 2 s } ), \, \forall \mathcal { J } _ { K } ^ { 2 s } \in J _ { K } ^ { 2 s } \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \, \end{pmatrix},$$

$$\text{we have} \quad & y _ { 1 } ^ { * } = C A _ { 0 } ^ { * } + C B u _ { 0 } ^ { * } \\ & y _ { 1 } = C A _ { 0 } + C B \bar { u } _ { 0 } + e _ { 0 }, \ \| e _ { 0 } \| _ { \ell _ { 2 } } \leq \epsilon. & ( 6 0 ) \\ & y _ { 1 } ^ { * } = y _ { 1 } + e _ { 0 } ^ { * }, \ \| e _ { 0 } ^ { * } \| _ { \ell _ { 2 } } \leq \epsilon \\ \text{satisfies the RIP condition} \, ( 7 ) \, \text{with isometr constant} \, \delta _ { \lambda _ { \lambda } } < \sqrt { 2 } - 1. \, \text{with the same annroach}$$

where ‖ e ∗ k ‖ /lscript 2 ≤ /epsilon1 . Based on assumptions that rank ( O K ) = n and rank ([ O K J 2 s K ]) = n + rank ( J 2 s K ) , ∀J 2 s K ∈ J 2 s K we can project the above equation using the projection ( I -P J 2 s K ) where P J 2 s K = J 2 s K ( J 2 s T K J 2 s K ) -1 J 2 s T K . It is straightforward to verify that ( I -P J 2 s K ) J 2 s K = 0 and therefore there exists a C J such that ‖ r ∗ 0 -¯ r 0 ‖ /lscript 2 ≤ C /epsilon1 J . After finding the error bound for r ∗ 0 , sequentially we can find the error bound for the input vectors at each time. For instance at k = 1 , we have

Because the matrix CB satisfies the RIP condition (7) with isometry constant δ 2 s &lt; √ 2 -1 , with the same approach used in Appendices B and D, it is straightforward to verify that there exists a C k such that ‖ u ∗ k -¯ u k ‖ /lscript 2 ≤ C /epsilon1 k , which means that always the recovered sparse input is upper bounded by a constant, C s multiple of the observation error.

## ACKNOWLEDGMENTS

We would like to thank Professor Humberto Gonzalez (WUSTL) for helpful input and discussions. ShiNung Ching holds a Career Award at the Scientific Interface from the Burroughs-Wellcome Fund. This work was partially supported by AFOSR 15RT0189, NSF ECCS 1509342 and NSF CMMI 1537015, from the US Air Force Office of Scientific Research and the US National Science Foundation, respectively.

## REFERENCES

- [1] E. J. Cand` es and M. B. Wakin, 'An introduction to compressive sampling,' IEEE Signal Process. Mag. , vol. 25, no. 2, pp. 21-30, 2008.
- [2] Y. C. Eldar and G. Kutyniok, Compressed sensing: theory and applications . Cambridge University Press, 2012.
- [3] J. Haupt, W. U. Bajwa, M. Rabbat, and R. Nowak, 'Compressed sensing for networked data,' IEEE Signal Process. Mag. , vol. 25, no. 2, pp. 92-101, 2008.
- [4] D. L. Donoho, 'For most large underdetermined systems of linear equations the minimal l 1 norm solution is also the sparsest solution,' Comm. Pure Appl. Math. , vol. 59, no. 6, pp. 797-829, 2006.
- [5] E. J. Cand` es, J. Romberg, and T. Tao, 'Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,' IEEE Trans. Inf. Theory , vol. 52, no. 2, pp. 489-509, 2006.
- [6] E. J. Candes and T. Tao, 'Decoding by linear programming,' IEEE Trans. Inf. Theory , vol. 51, no. 12, pp. 4203-4215, 2005.

- [7] E. J. Candes, J. K. Romberg, and T. Tao, 'Stable signal recovery from incomplete and inaccurate measurements,' Comm. Pure Appl. Math. , vol. 59, no. 8, pp. 1207-1223, 2006.
- [8] P. C. Petrantonakis and P. Poirazi, 'A compressed sensing perspective of hippocampal function,' Frontiers in Systems Neuroscience , vol. 8, 2014.
- [9] X. X. Wei and A. A. Stocker, 'A bayesian observer model constrained by efficient coding can explain'anti-bayesian'percepts,' Nat. Neurosci. , vol. 18, no. 10, pp. 1509-1517, 2015.
- [10] B. A. Olshausen et al. , 'Emergence of simple-cell receptive field properties by learning a sparse code for natural images,' Nature , vol. 381, no. 6583, pp. 607-609, 1996.
- [11] V. J. Barranca, G. Kovaˇ ciˇ c, D. Zhou, and D. Cai, 'Network dynamics for optimal compressive-sensing input-signal recovery,' Phys. Rev. E , vol. 90, no. 4, p. 042908, 2014.
- [12] --, 'Sparsity and compressed coding in sensory systems.' PLoS Computational Biology , vol. 10, no. 8, 2014.
- [13] N. Vaswani, 'Kalman filtered compressed sensing,' in Proc. 15th IEEE International Conference on Image Processing , 2008, pp. 893-896.
- [14] A. Charles, M. S. Asif, J. Romberg, and C. Rozell, 'Sparsity penalties in dynamical system estimation,' in Proc. 45th IEEE Annual Conference on Information Sciences and Systems (CISS), , 2011, pp. 1-6.
- [15] M. B. Wakin, B. M. Sanandaji, and T. L. Vincent, 'On the observability of linear systems from random, compressive measurements,' in Proc. 49th IEEE Conference on Decision and Control (CDC) , 2010, pp. 4447-4454.
- [16] B. M. Sanandaji, T. L. Vincent, M. B. Wakin, R. T´ oth, and K. Poolla, 'Compressive system identification of lti and ltv arx models,' in Proc. 50th IEEE Conf. on Decision and Control and European Control Conference (CDC-ECC) , 2011, pp. 791-798.
- [17] D. Napoletani and T. D. Sauer, 'Reconstructing the topology of sparsely connected dynamical networks,' Phys. Rev. E , vol. 77, no. 2, p. 026103, 2008.

[18]

Y. Shoukry, P. Nuzzo, A. Puggelli, A. L. Sangiovanni-Vincentelli, S. A. Seshia, and P. Tabuada, 'Secure state estimation under sensor attacks: A satisfiability modulo theory approach,'

arXiv preprint arXiv:1412.4324

,

2014.

- [19] H. Fawzi, P. Tabuada, and S. Diggavi, 'Secure estimation and control for cyber-physical systems under adversarial attacks,' IEEE Trans. Automatic Control , vol. 59, no. 6, pp. 1454-1467, 2014.
- [20] D. E. Ba, B. Babadi, P. L. Purdon, and E. N. Brown, 'Exact and stable recovery of sequences of signals with sparse increments via differential l 1 minimization,' in Proc. Advances in Neural Information Processing Systems (NIPS) , 2012, pp. 2636-2644.
- [21] S. Sefati, N. J. Cowan, and R. Vidal, 'Linear systems with sparse inputs: Observability and input recovery,' in Proc. IEEE American Control Conference (ACC) , 2015, pp. 5251-5257.
- [22] H. Jaeger, 'Short term memory in echo state networks,' GMD report, German National Research Center for Information Technology , 2001.
- [23] O. L. White, D. D. Lee, and H. Sompolinsky, 'Short-term memory in orthogonal neural networks,' Phys. Rev. Lett. , vol. 92, no. 14, p. 148102, 2004.
- [24] S. Ganguli, D. Huh, and H. Sompolinsky, 'Memory traces in dynamical systems,' Proceedings of the National Academy of Sciences , vol. 105, no. 48, pp. 18 970-18 975, 2008.
- [25] M. Hermans and B. Schrauwen, 'Memory in linear recurrent neural networks in continuous time,' Neural Networks , vol. 23, no. 3,
- pp. 341-355, 2010.
- [26] E. Wallace, H. R. Maei, and P. E. Latham, 'Randomly connected networks have short temporal memory,' Neural Comput. , vol. 25, no. 6, pp. 1408-1439, 2013.

[27]

S. Ganguli and H. Sompolinsky, 'Short-term memory in neuronal networks through dynamical compressed sensing,' in

Proc. Advances in neural information processing systems

,

2010, pp. 667-675.

- [28] A. S. Charles, H. L. Yap, and C. J. Rozell, 'Short-term memory capacity in networks via the restricted isometry property,' Neural Comput. , vol. 26, no. 6, pp. 1198-1235, 2014.
- [29] I. Ito, R. C.-Y. Ong, B. Raman, and M. Stopfer, 'Sparse odor representation and olfactory learning.' Nat. Neurosci. , vol. 11, no. 10, pp. 1177-1184, Oct 2008.
- [30] B. Raman, J. Joseph, J. Tang, and M. Stopfer, 'Temporally diverse firing patterns in olfactory receptor neurons underlie spatiotemporal neural codes for odors.' J. Neurosci. , vol. 30, no. 6, pp. 1994-2006, Feb 2010.

[31]

S.

Ostojic,

N. Brunel, and V.

Hakim, 'How connectivity, background

activity, and synaptic

properties shape

the cross-correlation

between spike trains,'

J.

Neurosci.

,

vol. 29, no. 33, pp. 10 234-10 253, 2009.

- [32] M. Kafashan, B. J. Palanca, and S. Ching, 'Bounded-observation kalman filtering of correlation in multivariate neural recordings,' in Proc. 36th Annu. Int. Conf. Eng. Med. Biol. , 2014.
- [33] L. F. Abbott, 'Lapicques introduction of the integrate-and-fire model neuron (1907),' Brain Res. Bull. , vol. 50, no. 5, pp. 303-304, 1999.
- [34] P. Dayan and L. Abbott, Theoretical neuroscience: computational and mathematical modeling of neural systems , ser. Comput. Neurosci.
- Cambridge, MA, USA: Massachusetts Institute of Technology Press, 2005.
- [35] E. M. Izhikevich et al. , 'Simple model of spiking neurons,' IEEE Trans. Neural Netw. , vol. 14, no. 6, pp. 1569-1572, 2003.
- [36] M. Kafashan, K. Q. Lepage, and S. Ching, 'Node selection for probing connections in evoked dynamic networks,' in Proc. 53nd IEEE Annu. Conf. Decision and Control (CDC) , 2014.
- [37] M. Kafashan and S. Ching, 'Optimal stimulus scheduling for active estimation of evoked brain networks,' J. Neural Eng. , vol. 12, no. 6, p. 066011, 2015.
- [38] R. J. Douglas and K. A. Martin, 'Recurrent neuronal circuits in the neocortex,' Curr. Biol. , vol. 17, no. 13, pp. R496-R500, 2007.
- [39] T. Kohonen and E. Oja, 'Fast adaptive formation of orthogonalizing filters and associative memory in recurrent networks of neuron-like elements,' Biol. Cybern. , vol. 21, no. 2, pp. 85-95, 1976.
- [40] H. S. Seung, D. D. Lee, B. Y. Reis, and D. W. Tank, 'Stability of the memory of eye position in a recurrent network of conductance-based model neurons,' Neuron , vol. 26, no. 1, pp. 259-271, 2000.

- [41] N. F. G¨ uler, E. D. Ubeyli, and I. G¨ uler, ¨ ˙ 'Recurrent neural networks employing lyapunov e xponents for EEG signals classification,' Expert Syst. Appl. , vol. 29, no. 3, pp. 506-514, 2005.
- [42] C. W. Omlin and C. L. Giles, 'Extraction of rules from discrete-time recurrent neural networks,' Neural Netw. , vol. 9, no. 1, pp. 41-52, 1996.
- [43] B. Ghanem and N. Ahuja, 'Sparse coding of linear dynamical systems with an application to dynamic texture recognition,' in Proc. 20th IEEE Int. Conf. Pattern Recog. (ICPR) , 2010, pp. 987-990.
- [44] X. Wei, H. Shen, and M. Kleinsteuber, 'An adaptive dictionary learning approach for modeling dynamical textures,' in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP) . IEEE, 2014, pp. 3567-3571.
- [45] L. Li, 'Fast algorithms for mining co-evolving time series,' Carnegie Inst. Tech., Dept. Computer Science, Tech. Rep. CMU-CS-11-127., 2011.
- [46] Y. Tao, C. Faloutsos, D. Papadias, and B. Liu, 'Prediction and indexing of moving objects with unknown motion patterns,' in Proc. ACM SIGMOD Int. Conf. Management of data , 2004, pp. 611-622.
- [47] S. Muthukrishnan, Data streams: Algorithms and applications . New Brunswick, NJ, USA: Now Publishers Inc, 2005.
- [48] R. G. Parker and R. L. Rardin, Discrete optimization . San Diego, CA, USA: Academic Press Professional, Inc., 1988.
- [49] E. J. Candes, 'The restricted isometry property and its implications for compressed sensing,' Comptes Rendus Mathematique , vol. 346, no. 9, pp. 589-592, 2008.
- [50] E. J. Candes and T. Tao, 'Near-optimal signal recovery from random projections: Universal encoding strategies?' IEEE Trans. Inf. Theory , vol. 52, no. 12, pp. 5406-5425, 2006.
- [51] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, 'A simple proof of the restricted isometry property for random matrices,' Constr. Approx. , vol. 28, no. 3, pp. 253-263, 2008.
- [52] S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann, 'Uniform uncertainty principle for bernoulli and subgaussian ensembles,' Constr. Approx. , vol. 28, no. 3, pp. 277-289, 2008.
- [53] E. Candes, L. Demanet, D. Donoho, and L. Ying, 'Fast discrete curvelet transforms,' Multiscale Modeling &amp; Simulation , vol. 5, no. 3, pp. 861-899, 2006.
- [54] E. J. Cand` es and D. L. Donoho, 'New tight frames of curvelets and optimal representations of objects with piecewise c2 singularities,' Commun. Pure Appl. Math. , vol. 57, no. 2, pp. 219-266, 2004.
- [55] I. CVX Research, 'CVX: Matlab software for disciplined convex programming, version 2.0,' Aug. 2012.
- [56] M. C. Grant and S. P. Boyd, 'Graph implementations for nonsmooth convex programs,' in Recent Advances in Learning and Control . Springer, 2008, pp. 95-110.
- [57] A. L. Barth and J. F. Poulet, 'Experimental evidence for sparse firing in the neocortex,' Trends in Neurosci. , vol. 35, no. 6, pp. 345-355, 2012.
- [58] D. J. Watts and S. H. Strogatz, 'Collective dynamics of small-worldnetworks,' Nature , vol. 393, no. 6684, pp. 440-442, 1998.
- [59] P. D. King, J. Zylberberg, and M. R. DeWeese, 'Inhibitory interneurons decorrelate excitatory cells to drive sparse code formation in a spiking model of v1,' J. Neurosci. , vol. 33, no. 13, pp. 5475-5485, 2013.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0202v2-figure-2c513160-d24e-40e5-97f0-76955f715137.jpg)
MohammadMehdi Kafashan Anirban Nandi ShiNung Ching
Analysis of Recurrent Linear Networks for Enabling Compressed Sensing of Time-Varying Signals
Recent interest has developed around the problem of dynamic compressed
sensing, or the recovery of time-varying, sparse signals from limited
observations. In this paper, we study how the dynamics of recurrent networks,
formulated as general dynamical systems, mediate the recoverability of such
signals. We specifically consider the problem of recovering a high-dimensional
network input, over time, from observation of only a subset of the network
states (i.e., the network output). Our goal is to ascertain how the network
dynamics lead to performance advantages, particularly in scenarios where both
the input and output are corrupted by disturbance and noise, respectively. For
this scenario, we develop bounds on the recovery performance in terms of the
dynamics. Conditions for exact recovery in the absence of noise are also
formulated. Through several examples, we use the results to highlight how
different network characteristics may trade off toward enabling dynamic
compressed sensing and how such tradeoffs may manifest naturally in certain
classes of neuronal networks.