Search

This paper addresses the behavior of a classical multiantenna GLRT test that allows to detect the presence of a known signal corrupted by a multipath propagation channel and by an additive temporally white Gaussian noise with unknown spatial covariance matrix. The paper is focused on the case where the number of sensors M is large, and of the same order of magnitude as the sample size N, a context which is modeled by the large system asymptotic regime M \rightarrow +\infty , N \rightarrow +\infty in such a way that M/N \rightarrow c for c \in (0,+\infty ). The purpose of this paper is to study the behaviour of a GLRT statistics in this regime, and to show that the corresponding theoretical analysis allows to accurately predict the performance of the test when M and N are of the same order of magnitude. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of cooperative localization in mobile networks. In static networks, node locations can be obtained from pairwise distance measurements using the classical multidimensional scaling (MDS) approach. This paper introduces a modified MDS framework that also incorporates relative velocity measurements if available in mobile networks. The proposed cost function is minimized via a low complexity majorization algorithm. A distributed variant of the proposed algorithm is also outlined for use in large resource-constrained multi-hop networks. The proposed algorithm incurs low computational and communication cost, and handles practical constraints such as missing measurements and variable node velocities. Simulation results corroborate the performance gains obtained by the proposed algorithm over state-of-the-art localization algorithms. [ABSTRACT FROM AUTHOR]

The paper is concerned with distributed learning in large-scale games. The well-known fictitious play (FP) algorithm is addressed, which, despite theoretical convergence results, might be impractical to implement in large-scale settings due to intense computation and communication requirements. An adaptation of the FP algorithm, designated as the empirical centroid fictitious play (ECFP), is presented. In ECFP players respond to the centroid of all players’ actions rather than track and respond to the individual actions of every player. Convergence of the ECFP algorithm in terms of average empirical frequency (a notion made precise in the paper) to a subset of the Nash equilibria is proven under the assumption that the game is a potential game with permutation invariant potential function. A more general formulation of ECFP is then given (which subsumes FP as a special case) and convergence results are given for the class of potential games. Furthermore, a distributed formulation of the ECFP algorithm is presented, in which, players endowed with a (possibly sparse) preassigned communication graph, engage in local, non-strategic information exchange to eventually agree on a common equilibrium. Convergence results are proven for the distributed ECFP algorithm. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate the design of distributed detection networks in the presence of an eavesdropper (Eve). We consider the problem of designing binary sensor quantizers that maximize the Kullback-Leibler (KL) divergence at the fusion center (FC), when subject to a tolerable constraint on the KL divergence at Eve. We assume that the channels between the sensors and the FC (likewise the channels between the sensors and the Eve) are modeled as binary symmetric channels (BSCs). In the case of i.i.d. received symbols at both the FC and Eve, we prove that the structure of the optimal binary quantizers is a likelihood ratio test (LRT). We also present an algorithm to find the threshold of the optimal LRT, and illustrate it for the case of Additive white Gaussian noise (AWGN) observation models at the sensors. In the case of non-i.i.d. received symbols at both FC and Eve, we propose a dynamic-programming based algorithm to find efficient quantizers at the sensors. Numerical results are presented to illustrate the performance of the proposed network. [ABSTRACT FROM AUTHOR]

This paper focuses on the development of novel greedy techniques for distributed learning under sparsity constraints. Greedy techniques have widely been used in centralized systems due to their low computational requirements and at the same time their relatively good performance in estimating sparse parameter vectors/signals. The paper reports two new algorithms in the context of sparsity-aware learning. In both cases, the goal is first to identify the support set of the unknown signal and then to estimate the nonzero values restricted to the active support set. First, an iterative greedy multistep procedure is developed, based on a neighborhood cooperation strategy, using batch processing on the observed data. Next, an extension of the algorithm to the online setting, based on the diffusion LMS rationale for adaptivity, is derived. Theoretical analysis of the algorithms is provided, where it is shown that the batch algorithm converges to the unknown vector if a Restricted Isometry Property (RIP) holds. Moreover, the online version converges in the mean to the solution vector under some general assumptions. Finally, the proposed schemes are tested against recently developed sparsity-promoting algorithms and their enhanced performance is verified via simulation examples. [ABSTRACT FROM PUBLISHER]

In this paper, we extend the generalized approximate message passing (G-AMP) approach, originally proposed for high-dimensional generalized-linear regression in the context of compressive sensing, to the generalized-bilinear case, which enables its application to matrix completion, robust PCA, dictionary learning, and related matrix-factorization problems. Here, in Part I of a two-part paper, we derive our Bilinear G-AMP (BiG-AMP) algorithm as an approximation of the sum-product belief propagation algorithm in the high-dimensional limit, where central-limit theorem arguments and Taylor-series approximations apply, and under the assumption of statistically independent matrix entries with known priors. In addition, we propose an adaptive damping mechanism that aids convergence under finite problem sizes, an expectation-maximization (EM)-based method to automatically tune the parameters of the assumed priors, and two rank-selection strategies. In Part II of the paper, we will discuss the specializations of EM-BiG-AMP to the problems of matrix completion, robust PCA, and dictionary learning, and we will present the results of an extensive empirical study comparing EM-BiG-AMP to state-of-the-art algorithms on each problem. [ABSTRACT FROM PUBLISHER]

The multitask diffusion LMS is an efficient strategy to simultaneously infer, in a collaborative manner, multiple parameter vectors. Existing works on multitask problems assume that all agents respond to data synchronously. In several applications, agents may not be able to act synchronously because networks can be subject to several sources of uncertainties such as changing topology, random link failures, or agents turning on and off for energy conservation. In this paper, we describe a model for the solution of multitask problems over asynchronous networks and carry out a detailed mean and mean-square error analysis. Results show that sufficiently small step-sizes can still ensure both stability and performance. Simulations and illustrative examples are provided to verify the theoretical findings. [ABSTRACT FROM AUTHOR]

This paper proposes generalized context modeling (GCM) for heterogeneous data compression. The proposed model extends the suffix of predicted subsequences in classic context modeling to arbitrary combinations of symbols in multiple directions. To address the selection of contexts, GCM constructs a model graph with a combinatorial structuring of finite order combination of predicted symbols as its nodes. The estimated probability for prediction is obtained by weighting over a class of context models that contain all the occurrences of nodes in the model graph. Moreover, separable context modeling in each direction is adopted for efficient prediction. To find optimal class of context models for prediction, the normalized maximum likelihood (NML) function is developed to estimate their structures and parameters, especially for heterogeneous data with large sizes. Furthermore, it is refined by context pruning to exclude the redundant models. Such model selection is optimal in the sense of minimum description length (MDL) principle, whose divergence is proven to be consistent with the actual distribution. It is shown that upper bounds of model redundancy for GCM are irrelevant to the size of data. GCM is validated in an extensive field of applications, e.g., Calgary corpus, executable files, and genomic data. Experimental results show that it outperforms most state-of-the-art context modeling algorithms reported. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a new class of techniques to identify periodicities in data. We target the period estimation directly rather than inferring the period from the signal’s spectrum. By doing so, we obtain several advantages over the traditional spectrum estimation techniques such as DFT and MUSIC. Apart from estimating the unknown period of a signal, we search for finer periodic structure within the given signal. For instance, it might be possible that the given periodic signal was actually a sum of signals with much smaller periods. For example, adding signals with periods 3, 7, and 11 can give rise to a period 231 signal. We propose methods to identify these “hidden periods” 3, 7, and 11. We first propose a new family of square matrices called Nested Periodic Matrices (NPMs), having several useful properties in the context of periodicity. These include the DFT, Walsh–Hadamard, and Ramanujan periodicity transform matrices as examples. Based on these matrices, we develop high dimensional dictionary representations for periodic signals. Various optimization problems can be formulated to identify the periods of signals from such representations. We propose an approach based on finding the least l2 norm solution to an under-determined linear system. Alternatively, the period identification problem can also be formulated as a sparse vector recovery problem and we show that by a slight modification to the usual l1 norm minimization techniques, we can incorporate a number of new and computationally simple dictionaries. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel framework for decentralized, online learning by many learners. At each moment of time, an instance characterized by a certain context may arrive to each learner; based on the context, the learner can select one of its own actions (which gives a reward and provides information) or request assistance from another learner. In the latter case, the requester pays a cost and receives the reward but the provider learns the information. In our framework, learners are modeled as cooperative contextual bandits. Each learner seeks to maximize the expected reward from its arrivals, which involves trading off the reward received from its own actions, the information learned from its own actions, the reward received from the actions requested of others and the cost paid for these actions—taking into account what it has learned about the value of assistance from each other learner. We develop distributed online learning algorithms and provide analytic bounds to compare the efficiency of these with algorithms with the complete knowledge (oracle) benchmark (in which the expected reward of every action in every context is known by every learner). Our estimates show that regret—the loss incurred by the algorithm—is sublinear in time. Our theoretical framework can be used in many practical applications including Big Data mining, event detection in surveillance sensor networks and distributed online recommendation systems. [ABSTRACT FROM PUBLISHER]

This paper studies distributed primal-dual strategies for adaptation and learning over networks from streaming data. Two first-order methods are considered based on the Arrow-Hurwicz (AH) and augmented Lagrangian (AL) techniques. Several revealing results are discovered in relation to the performance and stability of these strategies when employed over adaptive networks. The conclusions establish that the advantages that these methods exhibit for deterministic optimization problems do not necessarily carry over to stochastic optimization problems. It is found that they have narrower stability ranges and worse steady-state mean-square-error performance than primal methods of the consensus and diffusion type. It is also found that the AH technique can become unstable under a partial observation model, while the other techniques are able to recover the unknown under this scenario. A method to enhance the performance of AL strategies is proposed by tying the selection of the step-size to their regularization parameter. It is shown that this method allows the AL algorithm to approach the performance of consensus and diffusion strategies but that it remains less stable than these other strategies. [ABSTRACT FROM PUBLISHER]

Stochastic approximation techniques play an important role in solving many problems encountered in machine learning or adaptive signal processing. In these contexts, the statistics of the data are often unknown a priori or their direct computation is too intensive, and they have thus to be estimated online from the observed signals. For batch optimization of an objective function being the sum of a data fidelity term and a penalization (e.g., a sparsity promoting function), Majorize-Minimize (MM) methods have recently attracted much interest since they are fast, highly flexible, and effective in ensuring convergence. The goal of this paper is to show how these methods can be successfully extended to the case when the data fidelity term corresponds to a least squares criterion and the cost function is replaced by a sequence of stochastic approximations of it. In this context, we propose an online version of an MM subspace algorithm and we study its convergence by using suitable probabilistic tools. Simulation results illustrate the good practical performance of the proposed algorithm associated with a memory gradient subspace, when applied to both nonadaptive and adaptive filter identification problems. [ABSTRACT FROM PUBLISHER]

We study the optimal design of graph filters (GFs) to implement arbitrary linear transformations between graph signals. GFs can be represented by matrix polynomials of the graph-shift operator (GSO). Since this operator captures the local structure of the graph, GFs naturally give rise to distributed linear network operators. In most setups, the GSO is given so that GF design consists fundamentally in choosing the (filter) coefficients of the matrix polynomial to resemble desired linear transformations. We determine spectral conditions under which a specific linear transformation can be implemented perfectly using GFs. For the cases where perfect implementation is infeasible, we address the optimization of the filter coefficients to approximate the desired transformation. Additionally, for settings where the GSO itself can be modified, we study its optimal design as well. After this, we introduce the notion of a node-variant GF, which allows the simultaneous implementation of multiple (regular) GFs in different nodes of the graph. This additional flexibility enables the design of more general operators without undermining the locality in implementation. Perfect and approximate designs are also studied for this new type of GFs. To showcase the relevance of the results in the context of distributed linear network operators, this paper closes with the application of our framework to two particular distributed problems: finite-time consensus and analog network coding. [ABSTRACT FROM PUBLISHER]

In the context of multiple change-points estimation, performance analysis of estimators such as the maximum likelihood is often difficult to assess since the regularity assumptions are not met. Focusing on the estimators variance, one can, however, use lower bounds on the mean square error. In this paper, we derive the so-called Weiss–Weinstein bound (WWB) that is known to be an efficient tool in signal processing to obtain a fair overview of the estimation behavior. Contrary to several works about performance analysis in the change-point literature, our study is adapted to multiple changes. First, useful formulas are given for a general estimation problem whatever the considered distribution of the data. Second, closed-form expressions are given in the cases of Gaussian observations with changes in the mean and/or the variance, and changes in the mean rate of a Poisson distribution. Furthermore, a semidefinite programming formulation of the minimization procedure is given in order to compute the tightest WWB. Specifically, it consists of finding the unique minimum volume covering the set constituted by hyperellipsoid elements that are generated using the derived candidate WWB matrices w.r.t. the so-called Loewner partial ordering. Finally, simulation results are provided to show the good behavior of the proposed bound. [ABSTRACT FROM PUBLISHER]

In this paper, we present a novel technique for the retrieval of the modes of a multicomponent signal using a time-frequency (TF) representation of the signal. Our approach is based on a novel ridge extraction method that takes into account the fact that the TF representation is both discrete in time and frequency, followed by a demodulation procedure. Numerical results show the benefits of the proposed approach for mode reconstruction in comparison to similar techniques that do not make use of demodulation. Furthermore, numerical investigations show that the proposed approach sharpens the TF representation on which it is built. [ABSTRACT FROM PUBLISHER]

This paper deals with the problem of adaptive vector subspace signal detection in partially homogeneous Gaussian disturbance and structured (unknown) deterministic interference within the framework of invariance theory. It is first proved that the Maximal Invariant Statistic (MIS) for the problem at hand is scalar-valued and coincides with the well-known adaptive normalized matched filter evaluated after data projection in the complementary subspace of the interfering signal. Second, the statistical characterization of the MIS under both hypotheses is derived. Then, it is shown the statistical equivalence of (two-step) generalized-likelihood ratio test, Rao and Wald tests, as well as the more recently considered Durbin and Gradient test, to the above statistic. Finally, simulation results are provided to confirm our findings and analyze the performance trend of the MIS with the relevant parameters. [ABSTRACT FROM PUBLISHER]

Extracting actionable intelligence from distributed, heterogeneous, correlated, and high-dimensional data sources requires run-time processing and learning both locally and globally. In the last decade, a large number of meta-learning techniques have been proposed in which local learners make online predictions based on their locally collected data instances, and feed these predictions to an ensemble learner, which fuses them and issues a global prediction. However, most of these works do not provide performance guarantees or, when they do, these guarantees are asymptotic. None of these existing works provide confidence estimates about the issued predictions or rate of learning guarantees for the ensemble learner. In this paper, we provide a systematic ensemble learning method called Hedged Bandits, which comes with both long-run (asymptotic) and short-run (rate of learning) performance guarantees. Moreover, our approach yields performance guarantees with respect to the optimal local prediction strategy, and is also able to adapt its predictions in a data-driven manner. We illustrate the performance of Hedged Bandits in the context of medical informatics and show that it outperforms numerous online and offline ensemble learning methods. [ABSTRACT FROM PUBLISHER]

The minimum mean-squared error (MMSE) is one of the most popular criteria for Bayesian estimation. Conversely, the signal-to-noise ratio (SNR) is a typical performance criterion in communications, radar, and generally detection theory. In this paper, we first formalize an SNR criterion to design an estimator, and then we prove that there exists an equivalence between MMSE and maximum-SNR estimators, for any statistics. We also extend this equivalence to specific classes of suboptimal estimators, which are expressed by a basis expansion model (BEM). Then, by exploiting an orthogonal BEM for the estimator, we derive the MMSE estimator constrained to a given quantization resolution of the noisy observations, and we prove that this suboptimal MMSE estimator tends to the optimal MMSE estimator that uses an infinite resolution of the observation. Besides, we derive closed-form expressions for the mean-squared error (MSE) and for the SNR of the proposed suboptimal estimators, and we show that these expressions constitute tight, asymptotically exact, bounds for the optimal MMSE, and maximum SNR. [ABSTRACT FROM PUBLISHER]

Compressive sampling (CS) is an emerging research area for the acquisition of sparse signals at a rate lower than the Shannon sampling rate. Recently, CS has been extended to the challenging problem of multidimensional data acquisition. In this context, block-sparse core tensors have been introduced as the natural multidimensional extension of block-sparse vectors. The $(M_1,\ldots,M_Q)$ block sparsity for a tensor assumes that Q$ support sets, characterized by M_q$ indices corresponding to the nonzero entries, fully describe the sparsity pattern of the considered tensor. In the context of CS with Gaussian measurement matrices, the Cramér–Rao bound (CRB) on the estimation accuracy of a Bernoulli-distributed block-sparse core tensor is derived. This prior assumes that each entry of the core tensor has a given probability to be nonzero, leading to random supports of truncated Binomial-distributed cardinalities. Based on the limit form of the Poisson distribution, an approximated CRB expression is given for large dictionaries and a highly block-sparse core tensor. Using the property that the mode unfolding matrices of a block-sparse tensor follow the multiple-measurement vectors (MMV) model with a joint sparsity pattern, a fast and accurate estimation scheme, called Beamformed mOde based Sparse Estimator (BOSE), is proposed in the second part of this paper. The main contribution of the BOSE is to “map” the MMV model onto the single MV model, thanks to beamforming techniques. Finally, the proposed performance bounds and the BOSE are applied in the context of CS to nonbandlimited multidimensional signals with separable sampling kernels and \text{2)} for multipath channels in a multiple-input multiple-output wireless communication scheme. [ABSTRACT FROM PUBLISHER]

Compressed sensing (CS) enables measurement reconstruction by using sampling rates below the Nyquist rate, as long as the amplitude vector of interest is sparse. In this paper, we first derive and analyze the Bayesian Cramér–Rao bound (BCRB) for the amplitude vector when the set of indices (the support) of its nonzero entries is known. We consider the following context: i) The dictionary is nonstochastic but randomly generated; ii) the number of measurements and the support cardinality grow to infinity in a controlled manner, i.e., the ratio of these quantities converges to a constant; iii) the support is random; and iv) the vector of nonzero amplitudes follow a multidimensional generalized normal distribution. Using results from random matrix theory, we obtain closed-form approximations of the BCRB. These approximations can be formulated in a very compact form in low and high SNR regimes. Second, we provide a statistical analysis of the variance and the statistical efficiency of the oracle linear mean-square-error (LMMSE) estimator. Finally, we present results from numerical investigations in the context of non-bandlimited finite-rate-of-innovation (FRI) signal sampling. We show that the performance of Bayesian mean-square error (BMSE) estimators that are aware of the cardinality of the support, such as OMP and CoSaMP, are in good agreement with the developed lower bounds in the high SNR regime. Conversely, sparse estimators exploiting only the knowledge of the parameter vector and the noise variance in form of a priori distributions of these parameters, like LASSO and BPDN, are not efficient at high SNR. However, at low SNR, their BMSE is lower than that of the former estimators and may be close to the BCRB. [ABSTRACT FROM AUTHOR]

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 paper, 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. [ABSTRACT FROM AUTHOR]

This paper revisits blind source separation of instantaneously mixed quasi-stationary sources (BSS-QSS), motivated by the observation that in certain applications (e.g., speech) there exist time frames during which only one source is active, or locally dominant. Combined with nonnegativity of source powers, this endows the problem with a nice convex geometry that enables elegant and efficient BSS solutions. Local dominance is tantamount to the so-called pure pixel/separability assumption in hyperspectral unmixing/nonnegative matrix factorization, respectively. Building on this link, a very simple algorithm called successive projection algorithm (SPA) is considered for estimating the mixing system in closed form. To complement SPA in the specific BSS-QSS context, an algebraic preprocessing procedure is proposed to suppress short-term source cross-correlation interference. The proposed procedure is simple, effective, and supported by theoretical analysis. Solutions based on volume minimization (VolMin) are also considered. By theoretical analysis, it is shown that VolMin guarantees perfect mixing system identifiability under an assumption more relaxed than (exact) local dominance—which means wider applicability in practice. Exploiting the specific structure of BSS-QSS, a fast VolMin algorithm is proposed for the overdetermined case. Careful simulations using real speech sources showcase the simplicity, efficiency, and accuracy of the proposed algorithms. [ABSTRACT FROM PUBLISHER]

Compressive sensing (CS) has been widely investigated in the cognitive radio (CR) literature in order to reduce the hardware cost of sensing wideband signals assuming prior knowledge of the sparsity pattern. However, the sparsity order of the channel occupancy is time-varying and the sampling rate of the CS receiver needs to be adjusted based on its value in order to fully exploit the potential of CS-based techniques. In this context, investigating blind sparsity order estimation (SOE) techniques is an open research issue. To address this, we study an eigenvalue-based compressive SOE technique using asymptotic random matrix theory. We carry out detailed theoretical analysis for the signal plus noise case to derive the asymptotic eigenvalue probability distribution function (aepdf) of the measured signal's covariance matrix for sparse signals. Subsequently, based on the derived aepdf expressions, we propose a technique to estimate the sparsity order of the wideband spectrum with compressive measurements using the maximum eigenvalue of the measured signal's covariance matrix. The performance of the proposed technique is evaluated in terms of normalized SOE Error (SOEE). It is shown that the sparsity order of the wideband spectrum can be reliably estimated using the proposed technique for a variety of scenarios. [ABSTRACT FROM PUBLISHER]

Oscillations of a bandlimited signal at a rate faster than the bandlimit are called “superoscillations” and have applications e.g. in superresolution and superdirectivity. The synthesis of superoscillating signals is a numerically difficult problem. Minimum energy superoscillatory signals seem attractive for applications because (i) the minimum-energy solution is unique (ii) it has the smallest energy cost (iii) it may yield a signal of the smallest possible amplitude. On the negative side, superoscillating functions of minimum-energy depend heavily on cancellation and give rise to expressions that have very large coefficients. Furthermore, these coefficients have to be found by solving equations that are very ill-conditioned. Surprisingly, we show that by dropping the minimum energy requirement practicality can be gained rather than lost. We give a method of constructing superoscillating signals that leads to coefficients and condition numbers that are smaller by several orders of magnitude than the minimum-energy solution, yet yields energies close to the minimum. In contrast with the minimum-energy method, which builds superoscillations by linearly combining functions with an ill-conditioned Gram matrix, our method combines orthonormal functions, the Gram matrix of which is obviously the identity. Another feature of the method is that it yields the superoscillatory signal that maximises the energy concentration in a given set, which may or may not include the superoscillatory segment. [ABSTRACT FROM PUBLISHER]

A mathematical framework for similarity recovery from threshold-based sampling based on the concept of quasi-isometry is introduced. The approach leads to a unified model of threshold-based sampling schemes which comprises “send-on-delta” (SOD), “leaky integrate-and-fire” or the psychophysical Weber–Fechner law as examples and gives raise to novel sampling schemes such as “Leaky SOD.” As a result, the input and the output spaces become metric spaces being linked by lower and upper bounds under general conditions which go beyond assumptions in the signal recovery context. In particular, the proposed approach allows us to estimate the signal reconstruction error by resampling the reconstructed signal and applying the quasi-isometric distance measure in the sample space. [ABSTRACT FROM PUBLISHER]

We consider the best-arm identification problem in multi-armed bandits, which focuses purely on exploration. A player is given a fixed budget to explore a finite set of arms, and the rewards of each arm are drawn independently from a fixed, unknown distribution. The player aims to identify the arm with the largest expected reward. We propose a general framework to unify sequential elimination algorithms, where the arms are dismissed iteratively until a unique arm is left. Our analysis reveals a novel performance measure expressed in terms of the sampling mechanism and number of eliminated arms at each round. Based on this result, we develop an algorithm that divides the budget according to a nonlinear function of remaining arms at each round. We provide theoretical guarantees for the algorithm, characterizing the suitable nonlinearity for different problem environments described by the number of competitive arms. Matching the theoretical results, our experiments show that the nonlinear algorithm outperforms the state-of-the-art. We finally study the side-observation model, where pulling an arm reveals the rewards of its related arms, and we establish improved theoretical guarantees in the pure-exploration setting. [ABSTRACT FROM PUBLISHER]

In this study, a multiple-comparison approach is developed for detecting faint hyperspectral sources. The detection method relies on a sparse and nonnegative representation on a highly coherent dictionary to track a spatially varying source. A robust control of the detection errors is ensured by learning the test statistic distributions on the data. The resulting control is based on the false discovery rate, to take into account the large number of pixels to be tested. This method is applied to data recently recorded by the three-dimensional spectrograph MultiUnit Spectrograph Explorer (MUSE). [ABSTRACT FROM PUBLISHER]

In passive monitoring using sensor networks, low energy supplies drastically constrain sensors in terms of calculation and communication abilities. Designing processing algorithms at the sensor level that take into account these constraints is an important problem in this context. Here we study the estimation of correlation functions between sensors using compressed acquisition and one-bit-quantization. The estimation is achieved directly using compressed samples, without considering any reconstruction of the signals. We show that if the signals of interest are far from white noise, estimation of the correlation using $M$ compressed samples out of $N\geq M$ can be more advantageous than estimation of the correlation using $M$ consecutive samples. The analysis consists of studying the asymptotic performance of the estimators at a fixed compression rate. We provide the analysis when the compression is realized by a random projection matrix composed of independent and identically distributed entries. The framework includes widely used random projection matrices, such as Gaussian and Bernoulli matrices, and it also includes very sparse matrices. However, it does not include subsampling without replacement, for which a separate analysis is provided. When considering one-bit-quantization as well, the theoretical analysis is not tractable. However, empirical evidence allows the conclusion that in practical situations, compressed and quantized estimators behave sufficiently correctly to be useful in, for example, time-delay estimation and model estimation. [ABSTRACT FROM AUTHOR]

We propose a simple stochastic process for modeling improper or noncircular complex-valued signals. The process is a natural extension of a complex-valued autoregressive process, extended to include a widely linear autoregressive term. This process can then capture elliptical, as opposed to circular, stochastic oscillations in a bivariate signal. The process is order one and is more parsimonious than alternative stochastic modeling approaches in the literature. We provide conditions for stationarity, and derive the form of the covariance and relation sequence of this model. We describe how parameter estimation can be efficiently performed both in the time and frequency domain. We demonstrate the practical utility of the process in capturing elliptical oscillations that are naturally present in seismic signals. [ABSTRACT FROM PUBLISHER]

We study compressed sensing (CS) signal reconstruction problems where an input signal is measured via matrix multiplication under additive white Gaussian noise. Our signals are assumed to be stationary and ergodic, but the input statistics are unknown; the goal is to provide reconstruction algorithms that are universal to the input statistics. We present a novel algorithmic framework that combines: 1) the approximate message passing CS reconstruction framework, which solves the matrix channel recovery problem by iterative scalar channel denoising; 2) a universal denoising scheme based on context quantization, which partitions the stationary ergodic signal denoising into independent and identically distributed (i.i.d.) subsequence denoising; and 3) a density estimation approach that approximates the probability distribution of an i.i.d. sequence by fitting a Gaussian mixture (GM) model. In addition to the algorithmic framework, we provide three contributions: 1) numerical results showing that state evolution holds for nonseparable Bayesian sliding-window denoisers; 2) an i.i.d. denoiser based on a modified GM learning algorithm; and 3) a universal denoiser that does not need information about the range where the input takes values from or require the input signal to be bounded. We provide two implementations of our universal CS recovery algorithm with one being faster and the other being more accurate. The two implementations compare favorably with existing universal reconstruction algorithms in terms of both reconstruction quality and runtime. [ABSTRACT FROM AUTHOR]

Compressed sensing (CS) is a promising emerging domain that outperforms the classical limit of the Shannon sampling theory if the measurement vector can be approximated as the linear combination of few basis vectors extracted from a redundant dictionary matrix. Unfortunately, in realistic scenario, the knowledge of this basis or equivalently of the entire dictionary is often uncertain, i.e., corrupted by a Basis Mismatch (BM) error. The consequence of the BM problem is that the estimation accuracy in terms of Bayesian Mean Square Error (BMSE) of popular sparse-based estimators collapses even if the support is perfectly estimated and in the high Signal to Noise Ratio (SNR) regime. This saturation effect considerably limits the effective viability of these estimation schemes. In the first part of this work, the Bayesian Cramér-Rao Bound (BCRB) is derived for CS model with unstructured BM. We show that the BCRB foresees the saturation effect of the estimation accuracy of standard sparse-based estimators as for instance the OMP, Cosamp or the BP. In addition, we provide an approximation of this BMSE threshold. In the second part and in the context of the structured BM model, a new estimation scheme called Bias-Correction Estimator (BiCE) is proposed and its statistical properties are studied. The BiCE acts as a post-processing estimation layer for any sparse-based estimator and mitigates considerably the BM degradation. Finally, the BiCE i) is a blind algorithm, i.e., is unaware of the uncorrupted dictionary matrix, ii) is generic since it can be associated to any sparse-based estimator, iii) is fast, i.e., the additional computational cost remains low, and iv) has good statistical properties. To illustrate our results and propositions, the BiCE is applied in the challenging context of the compressive sampling of non-bandlimited impulsive signals. [ABSTRACT FROM AUTHOR]

In the context of change-point detection, addressed by Total Variation minimization strategies, an efficient on-the-fly algorithm has been designed leading to exact solutions for univariate data. In this contribution, an extension of such an on-the-fly strategy to multivariate data is investigated. The proposed algorithm relies on the local validation of the Karush-Kuhn-Tucker conditions on the dual problem. Showing that the non-local nature of the multivariate setting precludes to obtain an exact on-the-fly solution, we devise an on-the-fly algorithm delivering an approximate solution, whose quality is controlled by a practitioner-tunable parameter, acting as a trade-off between quality and computational cost. Performance assessment shows that high quality solutions are obtained on-the-fly while benefiting of computational costs several orders of magnitude lower than standard iterative procedures. The proposed algorithm thus provides practitioners with an efficient multivariate change-point detection on-the-fly procedure. [ABSTRACT FROM PUBLISHER]

The problem of signal parameter estimation and tracking with measurement data of low resolution is considered. In comparison to an ideal receiver with infinite receive resolution, the performance loss of a simplistic receiver with 1-bit resolution is investigated. For the case where the measurement data is preprocessed by a symmetric hard-limiting device with 1-bit output, it is well-understood that the performance for low SNR channel parameter estimation degrades moderately by 2/\pi(-\1.96~ dB). Here, we show that the 1-bit quantization loss can be significantly smaller if information about the temporal evolution of the channel parameters is taken into account in the form of a state-space model. By the analysis of a Bayesian bound for the achievable tracking performance, we attain the result that the quantization loss in dB is in general smaller by a factor of two if the channel evolution is slow. For the low SNR regime, this is equivalent to a reduced loss of \sqrt2/\pi(-\0.98 dB). By simulating non-linear filtering algorithms for a satellite-based ranging application and a UWB channel estimation problem, both with low-complexity 1-bit analog-to-digital converter (ADC) at the receiver, we verify that the analytical characterization of the tracking error is accurate. This shows that the performance loss due to observations with low amplitude resolution can, in practice, be much less pronounced than indicated by classical results. Finally, we discuss the implication of the result for medium SNR applications like channel estimation in the context of mobile wireless communications. [ABSTRACT FROM PUBLISHER]

Piecewise, low-order polynomial, Riesz basis families are constructed such that they share the same coefficient functionals of smoother, orthonormal bases in a localized indexing subset. It is shown that a minimal cardinality basis codomain can be realized by inducing sparsity, via \ell_1 regularization, in the distributional derivatives of the basis functions and that the optimal construction can be found numerically by constrained binary optimization over a suitably large dictionary. Furthermore, it is shown that a subset of these solutions are equivalent to a specific, constrained analytical solution, derived via Sylvester-type Hadamard operators. [ABSTRACT FROM PUBLISHER]

We propose two adaptive filtering algorithms that combine sparsity-promoting schemes with data-selection mechanisms. Sparsity is promoted via some well-known nonconvex approximations to the l^0 norm in order to increase convergence speed of the algorithms when dealing with sparse/compressible signals. These approximations circumvent some difficulties of working with the l^0 norm, thus allowing the development of online data-selective algorithms. Data selection is implemented based on set-membership filtering, which yields robustness against noise and reduced computational burden. The proposed algorithms are analyzed in order to set properly their parameters to guarantee stability. In addition, we characterize their updating processes from a geometrical viewpoint. Simulation results show that the proposed algorithms outperform the state-of-the-art algorithms designed to exploit sparsity. [ABSTRACT FROM PUBLISHER]