Search

The development of algorithms for secure state estimation in vulnerable cyber-physical systems has been gaining attention in the last years. A consolidated assumption is that an adversary can tamper a relatively small number of sensors. In the literature, block-sparsity methods exploit this prior information to recover the attack locations and the state of the system. In this paper, we propose an alternative, Lasso-based approach and we analyse its effectiveness. In particular, we theoretically derive conditions that guarantee successful attack/state recovery, independently of established time sparsity patterns. Furthermore, we develop a sparse state observer, by starting from the iterative soft thresholding algorithm for Lasso, to perform online estimation. Through several numerical experiments, we compare the proposed methods to the state-of-the-art algorithms., Comment: \textcopyright 2024 the authors. This work has been accepted to IFAC for publication under a Creative Commons Licence CC-BY-NC-ND

This paper addresses the problem of recursive set-membership identification for linear time varying (LTV) systems when both input and output measurements are affected by bounded additive noise. First we formulate the problem of online computation of the parameter uncertainty intervals (PUIs) in terms of nonconvex polynomial optimization. Then, we propose a convex relaxation approach based on McCormick envelopes to solve the formulated problem to the global optimum by means of linear programming. The effectiveness of the proposed identification scheme is demonstrated by means of two simulation examples., Comment: Accepted for publication in the 2021 60th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE)

Recovering the digital input of a time-discrete linear system from its (noisy) output is a significant challenge in the fields of data transmission, deconvolution, channel equalization, and inverse modeling. A variety of algorithms have been developed for this purpose in the last decades, addressed to different models and performance/complexity requirements. In this paper, we implement a straightforward algorithm to reconstruct the binary input of a one-dimensional linear system with known probabilistic properties. Although suboptimal, this algorithm presents two main advantages: it works online (given the current output measurement, it decodes the current input bit) and has very low complexity. Moreover, we can theoretically analyze its performance: using results on convergence of probability measures, Markov Processes, and Iterated Random Functions we evaluate its long-time behavior in terms of mean square error.

The development of online algorithms to track time-varying systems has drawn a lot of attention in the last years, in particular in the framework of online convex optimization. Meanwhile, sparse time-varying optimization has emerged as a powerful tool to deal with widespread applications, ranging from dynamic compressed sensing to parsimonious system identification. In most of the literature on sparse time-varying problems, some prior information on the system's evolution is assumed to be available. In contrast, in this paper, we propose an online learning approach, which does not employ a given model and is suitable for adversarial frameworks. Specifically, we develop centralized and distributed algorithms, and we theoretically analyze them in terms of dynamic regret, in an online learning perspective. Further, we propose numerical experiments that illustrate their practical effectiveness.

We consider the problem of the recovery of a k-sparse vector from compressed linear measurements when data are corrupted by a quantization noise. When the number of measurements is not sufficiently large, different $k$-sparse solutions may be present in the feasible set, and the classical l1 approach may be unsuccessful. For this motivation, we propose a non-convex quadratic programming method, which exploits prior information on the magnitude of the non-zero parameters. This results in a more efficient support recovery. We provide sufficient conditions for successful recovery and numerical simulations to illustrate the practical feasibility of the proposed method.

The recovery of signals with finite-valued components from few linear measurements is a problem with widespread applications and interesting mathematical characteristics. In the compressed sensing framework, tailored methods have been recently proposed to deal with the case of finite-valued sparse signals. In this work, we focus on binary sparse signals and we propose a novel formulation, based on polynomial optimization. This approach is analyzed and compared to the state-of-the-art binary compressed sensing methods.

The sparse linear regression problem is difficult to handle with usual sparse optimization models when both predictors and measurements are either quantized or represented in low-precision, due to non-convexity. In this paper, we provide a novel linear programming approach, which is effective to tackle this problem. In particular, we prove theoretical guarantees of robustness, and we present numerical results that show improved performance with respect to the state-of-the-art methods.

l1 reweighting algorithms are very popular in sparse signal recovery and compressed sensing, since in the practice they have been observed to outperform classical l1 methods. Nevertheless, the theoretical analysis of their convergence is a critical point, and generally is limited to the convergence of the functional to a local minimum or to subsequence convergence. In this letter, we propose a new convergence analysis of a Lasso l1 reweighting method, based on the observation that the algorithm is an alternated convex search for a biconvex problem. Based on that, we are able to prove the numerical convergence of the sequence of the iterates generated by the algorithm. This is not yet the convergence of the sequence, but it is close enough for practical and numerical purposes. Furthermore, we propose an alternative iterative soft thresholding procedure, which is faster than the main algorithm.

In this paper, we bring together two trends that have recently emerged in sparse signal recovery: the problem of sparse signals that stem from finite alphabets and the techniques that introduce concave penalties. Specifically, we show that using a minimax concave penalty (MCP) the recovery of finite-valued sparse signals is enhanced with respect to classical Lasso, in terms of estimation accuracy, number of necessary measurements, and run time. We focus on problems where sparse signals can be recovered from few linear measurements, as stated in compressed sensing theory. We start by proposing a Lasso-kind functional with MCP, whose minimum is the desired signal in the noise-free case, under null space conditions. We analyze its robustness to noise as well. We then propose an efficient ADMM-based algorithm to search the minimum. The algorithm is proved to converge to the set of stationary points, and its performance is evaluated through numerical experiments, both on randomly generated data and on a real localization problem. Furthermore, in the noise-free case, it is possible to check the exactness of the solution, and we test a version of the algorithm that exploits this fact to look for the right signal.

We propose a new approach to the recovery of binary signals in compressed sensing, based on the local minimization of a non-convex cost functional. The desired signal is proved to be a local minimum of the functional under mild conditions on the sensing matrix and on the number of measurements. We develop a procedure to achieve the desired local minimum, and, finally, we propose numerical experiments that show the improvement obtained by the proposed approach with respect to the classical convex approach, i.e., Lasso.

Time-varying systems are a challenge in many scientific and engineering areas. Usually, estimation of time-varying parameters or signals must be performed online, which calls for the development of responsive online algorithms. In this paper, we consider this problem in the context of the sparse optimization; specifically, we consider the Elastic-net model, which promotes parsimonious solutions. Following the rationale in \cite{mok16}, we propose an online algorithm and we theoretically prove that it is successful in terms of dynamic regret. We then show an application to the problem of recursive identification of time-varying autoregressive models, in the case when the number of parameters to be estimated is unknown. Numerical results show the practical efficiency of the proposed method.

Compressive sensing promises to enable bandwidth-efficient on-board compression of astronomical data by lifting the encoding complexity from the source to the receiver. The signal is recovered off-line, exploiting GPUs parallel computation capabilities to speedup the reconstruction process. However, inherent GPU hardware constraints limit the size of the recoverable signal and the speedup practically achievable. In this work, we design parallel algorithms that exploit the properties of circulant matrices for efficient GPU-accelerated sparse signals recovery. Our approach reduces the memory requirements, allowing us to recover very large signals with limited memory. In addition, it achieves a tenfold signal recovery speedup thanks to ad-hoc parallelization of matrix-vector multiplications and matrix inversions. Finally, we practically demonstrate our algorithms in a typical application of circulant matrices: deblurring a sparse astronomical image in the compressed domain.

The problem of the distributed recovery of jointly sparse signals has attracted much attention recently. Let us assume that the nodes of a network observe different sparse signals with common support; starting from linear, compressed measurements, and exploiting network communication, each node aims at reconstructing the support and the non-zero values of its observed signal. In the literature, distributed greedy algorithms have been proposed to tackle this problem, among which the most reliable ones require a large amount of transmitted data, which barely adapts to realistic network communication constraints. In this work, we address the problem through a reweighted $\ell_1$ soft thresholding technique, in which the threshold is iteratively tuned based on the current estimate of the support. The proposed method adapts to constrained networks, as it requires only local communication among neighbors, and the transmitted messages are indices from a finite set. We analytically prove the convergence of the proposed algorithm and we show that it outperforms the state-of-the-art greedy methods in terms of balance between recovery accuracy and communication load.

The Voyager probes are the furthest, still active, spacecraft ever launched from Earth. During their 38-year trip, they have collected data regarding solar wind properties (such as the plasma velocity and magnetic field intensity). Unfortunately, a complete time evolution of the measured physical quantities is not available. The time series contains many gaps which increase in frequency and duration at larger distances. The aim of this work is to perform a spectral and statistical analysis of the solar wind plasma velocity and magnetic field using Voyager 2 data measured in 1979, when the gaps/signal ratio is of order of unity. This analysis is achieved using four different data reconstruction techniques: averages on linearly interpolated subsets, correlation of linearly interpolated data, compressed sensing spectral estimation, and maximum likelihood data reconstruction. With five frequency decades, the spectra we obtained have the largest frequency range ever computed at 5 astronomical units from the Sun; spectral exponents have been determined for all the components of the velocity and magnetic field fluctuations. Void analysis is also useful in recovering other spectral properties such as integral scales (see for instance Table 4) and, if the confidence level of the measurements is sufficiently high, the decay variation in the small scale range due, for instance, to dissipative effects., Comment: 11 pages, 7 figures

In this paper, we address the problem of distributed sparse recovery of signals acquired via compressed measurements in a sensor network. We propose a new class of distributed algorithms to solve Lasso regression problems, when the communication to a fusion center is not possible, e.g., due to communication cost or privacy reasons. More precisely, we introduce a distributed iterative soft thresholding algorithm (DISTA) that consists of three steps: an averaging step, a gradient step, and a soft thresholding operation. We prove the convergence of DISTA in networks represented by regular graphs, and we compare it with existing methods in terms of performance, memory, and complexity., Comment: Revised version. Main improvements: extension of the convergence theorem to regular graphs; new numerical results and comparisons with other algorithms

In this paper, we address the problem of simultaneous classification and estimation of hidden parameters in a sensor network with communications constraints. In particular, we consider a network of noisy sensors which measure a common scalar unknown parameter. We assume that a fraction of the nodes represent faulty sensors, whose measurements are poorly reliable. The goal for each node is to simultaneously identify its class (faulty or non-faulty) and estimate the common parameter. We propose a novel cooperative iterative algorithm which copes with the communication constraints imposed by the network and shows remarkable performance. Our main result is a rigorous proof of the convergence of the algorithm and a characterization of the limit behavior. We also show that, in the limit when the number of sensors goes to infinity, the common unknown parameter is estimated with arbitrary small error, while the classification error converges to that of the optimal centralized maximum likelihood estimator. We also show numerical results that validate the theoretical analysis and support their possible generalization. We compare our strategy with the Expectation-Maximization algorithm and we discuss trade-offs in terms of robustness, speed of convergence and implementation simplicity.

The aim of this paper is to propose an alternative method to solve a Fault Tolerant Control problem. The model is a linear system affected by a disturbance term: this represents a large class of technological faulty processes. The goal is to make the system able to tolerate the undesired perturbation, i.e., to remove or at least reduce its negative effects; such a task is performed in three steps: the detection of the fault, its identification and the consequent process recovery. When the disturbance function is known to be \emph{quantized} over a finite number of levels, the detection can be successfully executed by a recursive \emph{decoding} algorithm, arising from Information and Coding Theory and suitably adapted to the control framework. This technique is analyzed and tested in a flight control issue; both theoretical considerations and simulations are reported.