In this paper, our focus is on estimating the initial condition of a linear time-invariant (LTI) network from a set of state samples that are collected sparsely from a subset of subsystems aperiodically over some time interval. This problem is closely related to state observer design with sensing-constraints for linear dynamical networks. In Section , we apply tools from (finite) frame theory to reformulate the network observability problem and show that one can extract an observability frame from any given set of samples that solves the observability problem. This key idea allows us to cast observability condition as whether a set of vectors forms a frame for the Euclidean space. This is particularly useful as every frame element is labeled by where and when it was taken. In Section , two types of measures, namely, standard deviation and differential entropy of the estimation error, are utilized to quantify quality of estimation for a given observability frame. They are also useful when one desires to compare estimation quality of various sampling strategies for a given network.
We show that these estimation measures can be quantified using eigenvalues of the corresponding frame matrix. An important property of these estimation measures is that they are monotone with respect to the number of samples: by increasing the number of samples, the estimation measure does not deteriorate. In Section , we propose deterministic and randomized methods to generate observability frames for a given LTI network. It is shown that minimum required number of samples from each subsystem (location) depends on the degree of the minimal polynomial of the state matrix. We show in Section  that there are inherent fundamental limits on the best achievable levels of estimation quality, and intrinsic tradeoffs reveal an interplay between space-time samples: taking less samples (in average) per subsystem mandates collecting samples from more subsystems. In Section , we discuss three methods for frame sparsification: (i) sparsification by leverage scores, which is developed based on notions of spectral graph sparsification [1]}, (ii) random partitioning using Kadison-Singer paving solution [2]}, and (iii) greedy elimination using Sherman-Morrison rank-one update rule [3]}. In all these algorithms, we obtain explicit error bounds for estimation-quality loss. We assert that our bounds are rather conservative. The reason is that, contrary to the results of [1]}, [5]}, [6]}, [7]}, elements of a sparsified observability frame cannot be rescaled to compensate for estimation-quality loss. At the end, we support our theoretical finding by several simulation case studies. This paper is an outgrowth of its conference version [8]} and contains several new technical results, proofs, and simulation results. More specifically, we list some the main differences of the current work with [8]} as follows. First, the omitted proofs from [8]} have been added. Second, several results are new, including results in Sections  and , Subsections REF  and REF , Theorem REF , and the running time analysis and corresponding numerical experiment. Third, several existing results have been improved, e.g., the minimal required number of samples per location in Theorems REF  and REF  have been refined and improved. Moreover, The counterpart of Theorem 14 in [8]} (Theorem X) did not have a performance bound. In this work, we offer probabilistic guarantee for the outcome of sparsification. Forth, only a few sections from [8]} have been transferred to this draft and that has been done after a thorough revision to enhance coherency of our presentation. Some parts of [8]} have been completely eliminated, e.g., space-time tradeoffs. Fifth, this paper covers a more compressive literature review. 
