Search

The current trend of acquiring data pervasively calls for some data-selection strategy, particularly in the case a subset of the data does not bring enough innovation. In this paper, we present some extensions of the existing adaptive filtering algorithms enabling data selection, which also address the censorship of outliers measured through unexpected high estimation errors. The resulting algorithms allow the prescription of how often the acquired data are expected to be incorporated in the learning process based on some a priori assumptions regarding the environment data. A detailed derivation of how to implement the data selection in a computationally efficient way is provided along with the proper choice of the parameters inherent to the data-selective affine projection algorithms. Similar discussions lead to the proposal of the data-selective least mean square and data-selective recursive least squares algorithms. Simulation results show the effectiveness of the proposed algorithms for selecting the innovative data without sacrificing the estimation accuracy, while reducing the computational cost. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a wideband dictionary framework for estimating sparse signals. By formulating integrated dictionary elements spanning bands of the considered parameter space, one may efficiently find and discard large parts of the parameter space not active in the signal. After each iteration, the zero-valued parts of the dictionary may be discarded to allow a refined dictionary to be formed around the active elements, resulting in a zoomed dictionary to be used in the following iterations. Implementing this scheme allows for more accurate estimates, at a much lower computational cost, as compared to directly forming a larger dictionary spanning the whole parameter space or performing a zooming procedure using standard dictionary elements. Different from traditional dictionaries, the wideband dictionary allows for the use of dictionaries with fewer elements than the number of available samples without loss of resolution. The technique may be used on both one- and multidimensional signals, and may be exploited to refine several traditional sparse estimators, here illustrated with the LASSO and the SPICE estimators. Numerical examples illustrate the improved performance. [ABSTRACT FROM AUTHOR]

Detection of a signal under noise is a classical signal processing problem. When monitoring spatial phenomena under a fixed budget, i.e., either physical, economical, or computational constraints, the selection of a subset of available sensors, referred to as sparse sensing, that meets both the budget and performance requirements is highly desirable. Unfortunately, the subset selection problem for detection under dependent observations is combinatorial in nature, and suboptimal subset selection algorithms must be employed. In this work, different from the widely used convex relaxation of the problem, we leverage submodularity, the diminishing returns property, to provide practical algorithms suitable for large-scale subset selection. This is achieved by means of low-complexity greedy algorithms, which incur a reduced computational complexity compared to their convex counterparts. [ABSTRACT FROM AUTHOR]

Given a $d$ -dimensional array of size $n^d$ and an integer $p$ , the running max (or min) filter is the set of maximum (or minimum) elements within a $d$ -dimensional sliding window of edge length $p$ inside the array. This problem is useful in many signal processing applications such as pattern analysis, adaptive signal processing, and morphological analysis. The current best algorithm for computing the one-dimensional (1-D) max (or min) filter, due to the work of [H. Yuan and M. J. Atallah, “Running max/min filters using 1+o(1) comparisons per sample,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 12, pp. 2544–2548, Dec. 2011], uses $1+o(1)$ comparisons per sample in the worst case. As a direct consequence, the $d$ -dimensional max (or min) filter (max and min filters, respectively) can be computed in $d+o(1)$ ($2d+o(1)$ , respectively) comparisons per sample. In this paper, we first present an algorithm for computing $d$ -dimensional max and min filters simultaneously on i.i.d. inputs that uses $1.5+o(1)$ expected comparisons per sample. This is the first algorithm (on i.i.d. inputs) that gets rid of the dependence on $d$ in the dominating term, with respect to $n$ and $p$ , of the (expected) number of comparisons needed. It is also asymptotically optimal (when $d$ is a fixed constant as $n \rightarrow \infty$ and $p \rightarrow \infty$). We also consider the dynamic version of the problem of $d$ -dimensional max and min filters simultaneously on i.i.d. inputs where we want to maintain the filters after changes in the input array. We design a linear-sized data structure that stores precomputed information for efficient update using $O(p^{d-1}\log _2 p)$ expected comparisons per update. [ABSTRACT FROM AUTHOR]

Binary sequence sets with asymptotically optimal auto/cross correlation peak sidelobe level (PSL) growth have been known in the literature for a long time, and their construction has been studied both analytically and numerically. In contrast, it has been a long-standing problem whether we can construct a family of binary sequences whose auto-correlation PSL grows in an optimal manner. In this paper, we devise a construction method of binary sequences with asymptotically optimal PSL growth from the sequence sets with good correlation properties. A key component of the design follows from the observation that if the PSL of the sequence set grows optimally or nearly optimally, then the PSL of the constructed binary sequence will experience a similar growth as a consequence. The proposed construction is simple-to-implement, and is shown to be accomplished in polynomial time. With such a construction, we not only bridge the gap between analytical construction and computational search, but also pave the way to settle the long-standing design problem of binary sequences with an optimal growth of the auto-correlation PSL. [ABSTRACT FROM AUTHOR]

In this paper, we develop a new deflationary blind source extraction (BSE) algorithm that extracts source signals in a sequential fashion via the joint generalized eigenvectors of a set of covariance matrix pencils. The new concept of joint generalized eigenvector is defined. We prove that these vectors can be made unique and identical to the source extraction vectors with properly selected matrix pencils. To resolve the open problem of estimating joint generalized eigenvectors, we develop an approach based on the deflation operation and the proportional property of the joint generalized eigenvectors. Specifically, with the proportional property, we show that the estimation problem can be formulated as an optimization involving a quadratic cost function and a unit-rank matrix constraint. An efficient iterative algorithm is then developed by applying the gradient search, matrix shrinkage, deflation, and symmetry-preserving vectorization techniques. This algorithm estimates the joint generalized eigenvectors and conducts BSE sequentially. Its computational complexity and convergence are analyzed. Simulations demonstrate that this algorithm outperforms many typical BSE or blind source separation algorithms. In particular, the new algorithm is more robust to both heavy noise and ill-conditioned mixing matrices. [ABSTRACT FROM AUTHOR]

The immense amount of daily generated and communicated data presents unique challenges in their processing. Clustering, the grouping of data without the presence of groundtruth labels, is an important tool for drawing inferences from data. Subspace clustering (SC) is a relatively recent method that is able to successfully classify nonlinearly separable data in a multitude of settings. In spite of their high clustering accuracy, SC methods incur prohibitively high computational complexity when processing large volumes of high-dimensional data. Inspired by random sketching approaches for dimensionality reduction, the present paper introduces a randomized scheme for SC, termed Sketch-SC, tailored for large volumes of high-dimensional data. Sketch-SC accelerates the computationally heavy parts of state-of-the-art SC approaches by compressing the data matrix across both dimensions using random projections, thus enabling fast and accurate large-scale SC. Performance analysis as well as extensive numerical tests on real data corroborate the potential of Sketch-SC and its competitive performance relative to state-of-the-art scalable SC approaches. [ABSTRACT FROM AUTHOR]

We revisit the stochastic limited-memory Broyden- Fletcher-Goldfarb-Shanno (L-BFGS) algorithm. By proposing a new coordinate transformation framework for the convergence analysis, we prove improved convergence rates and computational complexities of the stochastic L-BFGS algorithms compared to previous works. In addition, we propose several practical ac- celeration strategies to speed up the empirical performance of such algorithms. We also provide theoretical analyses for most of the strategies. Experiments on large-scale logistic and ridge regression problems demonstrate that our proposed strategies yield significant improvements vis-à-vis competing state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

BigBand is a technique for wideband spectrum sensing (WSS) that can capture gigahertz of sparse spectrum in real time by using shifted multiple channels without sampling the signal at GS/s. In this paper, we focus on enforcing BigBand with the proposed improved algorithm, namely, AD-BigBand, for efficient and robust computation. AD-BigBand converts the nonlinear process (locating frequency and computing the spectrum value) of sparse WSS into two steps of solving linear equations. In particular, we define an r -degree frequency locator polynomial to rapidly locate nonzero frequencies. The computing complexity of the proposed method decreases from O(K{\log ^2}K ({{{n\log K} \over K}})^{\log K}) of shifted sampling based BigBand to O(K{\log ^2}K)$, where the $K$-sparse signals of bandwitdth $n$ are subsampled with arithmetic time-shifted sensing channels. We implement AD-BigBand on a commercial four-channel acquisition card. Experimental results show that AD-BigBand improves the WSS capabilities and exhibits higher processing speed and lower error spectrum construction rate than BigBand, especially in the case of relative low signal-to-noise ratio. [ABSTRACT FROM AUTHOR]

Conventional direction-of-arrival (DOA) estimation methods are sensitive to outlier measurements. Therefore, their performance may degrade substantially in the presence of impulsive noise. In this paper, we address the problem of DOA estimation in additive outliers from the perspective of sparse Bayesian learning (SBL). A Bayes-optimal algorithm is devised for robust DOA estimation, which can achieve excellent performance in terms of resolution and accuracy. To reduce the computational complexity of the SBL scheme, a fast alternating algorithm is also developed. New grid-refining procedures are further introduced into these two proposed algorithms to efficiently fix the off-grid gap. As our solutions do not require the prior knowledge of the number of sources and can resolve highly correlated or coherent sources, it is expected that they have higher applicability. Simulation results verify the outlier-robust performance of the SBL approach. [ABSTRACT FROM AUTHOR]

We propose a new single-RF differential space–time block coding using index shift keying (DSTBC-ISK), which is the first differential space–time modulation (DSTM) scheme that can simultaneously achieve the following three imperative objectives: First, forming a finite-cardinality transmit-signals set; second, retaining a single-stream maximum-likelihood (ML) detection complexity; and third, offering a beneficial transmit diversity gain. In order to make a fair comparison, we also conceive a low-complexity single-stream detector for DSM. Furthermore, in order to improve the performance of finite-cardinality DSTM schemes at higher throughputs, we propose to generalize both differential amplitude shift keying (DASK) and amplitude shift keying (ASK), which subsume the existing two-/four-level-ring star quadratic–amplitude modulation (QAM) solutions as special cases. As a result of using star QAM signaling, the power of the DSTM's signal matrix becomes variable. Against this background, we further develop bespoke ML, minimum mean squared error, and least-square detectors for DSTM using DASK/ASK. Our simulation results demonstrate that the proposed DSTBC-ISK is capable of achieving substantial diversity gains over DSM without eroding its low transceiver complexity. [ABSTRACT FROM AUTHOR]

Detection with high-dimensional multimodal data is a challenging problem when there are complex inter- and intra- modal dependencies. While several approaches have been proposed for dependent data fusion (e.g., based on copula theory), their advantages come at a high price in terms of computational complexity. In this paper, we treat the detection problem with compressive sensing (CS) where compression at each sensor is achieved via low-dimensional random projections. CS has recently been exploited to solve detection problems under various assumptions on the signals of interest; however, its potential for dependent data fusion has not been explored adequately. We exploit the capability of CS to capture statistical properties of uncompressed data in order to compute decision statistics for detection in the compressed domain. First, a Gaussian approximation is employed to perform likelihood ratio (LR) based detection with compressed data. In this approach, intermodal dependence is captured via a compressed version of the covariance matrix of the concatenated (temporally and spatially) uncompressed data vector. We show that, under certain conditions, this approach with a small number of compressed measurements per node leads to enhanced performance compared to detection with uncompressed data using widely considered suboptimal approaches. Second, we develop a nonparametric approach where a decision statistic based on the second order statistics of uncompressed data is computed in the compressed domain. The second approach is promising over the first approach and the other related nonparametric approaches when multimodal data is highly correlated at the expense of slightly increased computational complexity. [ABSTRACT FROM AUTHOR]

We propose an efficient algorithm to design waveforms via relative entropy for multiple-input-multiple-output radar in the presence of (signal-dependent) clutter. The proposed algorithm is devised under the framework of minorization-maximization. Unlike the existing algorithm employing a highly nonlinear function to minorize the objective function, the proposed algorithm uses a quadratic function as the minorizer, leading to a much lower computational cost per iteration. In addition, we exploit an accelerated scheme called squared iterative method, to enhance the convergence rate of the proposed algorithm. Moreover, we extend the proposed algorithm to deal with additional constraints (i.e., constant-modulus constraint, similarity constraint, or both). Particularly, the extension allows for a single-stage design of the constrained waveforms and achieves a larger relative entropy than the existing algorithm. Numerical results are provided to show that the proposed algorithm is computationally more efficient and outperforms the existing algorithm when designing the constrained waveforms. [ABSTRACT FROM AUTHOR]

This paper develops a novel algorithm, termed SPARse Truncated Amplitude flow (SPARTA), to reconstruct a sparse signal from a small number of magnitude-only measurements. It deals with what is also known as sparse phase retrieval (PR), which is NP-hard in general and emerges in many science and engineering applications. Upon formulating sparse PR as an amplitude-based nonconvex optimization task, SPARTA works iteratively in two stages: In stage one, the support of the underlying sparse signal is recovered using an analytically well-justified rule, and subsequently a sparse orthogonality-promoting initialization is obtained via power iterations restricted on the support; and in the second stage, the initialization is successively refined by means of hard thresholding based gradient-type iterations. SPARTA is a simple yet effective, scalable, and fast sparse PR solver. On the theoretical side, for any n-dimensional k-sparse (k ≪ n) signal x with minimum (in modulus) nonzero entries on the order of (1/√k)||x||2, SPARTA recovers the signal exactly (up to a global unimodular constant) from about k2 log n random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of k2 n log n with total runtime proportional to the time required to read the data, which improves upon the state of the art by at least a factor of k. Finally, SPARTA is robust against additive noise of bounded support. Extensive numerical tests corroborate markedly improved recovery performance and speedups of SPARTA relative to existing alternatives. [ABSTRACT FROM AUTHOR]

This paper considers the design of beamformers for a multiple-input single-output downlink system with per-antenna power constraints (PAPCs) that seek to mitigate the impact of the imperfections in the channel state information that is available at the base station. The goal of the design is to minimize the outage probability of specified signal-to-interference-and-noise ratio targets, and to do so at a low computational cost. The proposed design strategy provides an efficient way to handle PAPCs, in addition to a total power constraint, for a variety of precoding techniques, including the offset maximization approach to robust beamforming, and the nominal zero-forcing and maximum ratio transmission approaches. Through observations regarding the structure of the optimality conditions for each of the design formulations, low-complexity iterative algorithms that involve the evaluation of closed-form expressions are developed. In systems with a large number of antennas, the computational cost of some of these algorithms can be reduced to being linear in the number of antennas, without a significant degradation in performance. Simulation results show that the proposed robust designs can provide substantial reductions in the outage probability while satisfying the PAPCs. [ABSTRACT FROM AUTHOR]

This paper examines the mean-square error performance of diffusion stochastic algorithms under a generalized coordinate-descent scheme. In this setting, the adaptation step by each agent is limited to a random subset of the coordinates of its stochastic gradient vector. The selection of coordinates varies randomly from iteration to iteration and from agent to agent across the network. Such schemes are useful in reducing computational complexity at each iteration in power-intensive large data applications. They are also useful in modeling situations where some partial gradient information may be missing at random. Interestingly, the results show that the steady-state performance of the learning strategy is not always degraded, while the convergence rate suffers some degradation. The results provide yet another indication of the resilience and robustness of adaptive distributed strategies. [ABSTRACT FROM AUTHOR]

This paper presents methods to compare networks where relationships between pairs of nodes in a given network are defined. We define such network distance by searching for the optimal method to embed one network into another network, prove that such distance is a valid metric in the space of networks modulo permutation isomorphisms, and examine its relationship with other network metrics. The network distance defined can be approximated via multidimensional scaling; however, the lack of structure in networks results in suboptimal approximations. To alleviate such a problem, we consider methods to define the interiors of networks. We show that comparing interiors induced from a pair of networks yields the same result as the actual network distance between the original networks. Practical implications are explored by showing the ability to discriminate networks generated by different models. [ABSTRACT FROM AUTHOR]

This paper considers a wireless sensor network for locating a static target or tracking a dynamic target, which is characterized a priori by a Gaussian mixture distribution. An amplify-and-forward relay node acts as a wireless bridge in relaying the sensor's independent observations of the target to a fusion center (FC). Joint power allocation is considered for the sensors and relay to optimize a Bayesian filter, which is deployed at the FC for a global estimate of the target. The mean squared error of the Bayesian filter is already computationally intractable for fixed sensor and relay transmitter power, so power allocation to minimize its mean squared error is a very challenging problem. In this paper, the problem is addressed by an iterative procedure of very low computational complexity. Simulations are provided to support the efficiency of our proposed power allocation. [ABSTRACT FROM AUTHOR]

A fast gridless method for sparse frequency estimation in the presence of prior information is presented. It allows arbitrarily sampled data and has a significantly smaller complexity than the existing gridless sparse recovery methods. The proposed method achieves good frequency estimation accuracy and resolution performance in numerical simulations. It is also useful where no prior knowledge is available. [ABSTRACT FROM AUTHOR]

The Probability Hypothesis Density (PHD) and Cardinalized PHD (CPHD) filters are popular solutions to the multitarget tracking problem due to their low complexity and ability to estimate the number and states of targets in cluttered environments. The PHD filter propagates the first-order moment (i.e. mean) of the number of targets while the CPHD propagates the cardinality distribution in the number of targets, albeit for a greater computational cost. Introducing the Panjer point process, this paper proposes a Second-Order PHD (SO-PHD) filter, propagating the second-order moment (i.e., variance) of the number of targets alongside its mean. The resulting algorithm is more versatile in the modeling choices than the PHD filter, and its computational cost is significantly lower compared to the CPHD filter. This paper compares the three filters in statistical simulations which demonstrate that the proposed filter reacts more quickly to changes in the number of targets, i.e., target births and target deaths, than the CPHD filter. In addition, a new statistic for multiobject filters is introduced in order to study the correlation between the estimated number of targets in different regions of the state space, and propose a quantitative analysis of the spooky effect for the three filters. [ABSTRACT FROM PUBLISHER]

Distributed adaptive signal processing has attracted much attention in the recent decade owing to its effectiveness in many decentralized real-time applications in networked systems. Because many natural signals are highly sparse with most entries equal to zero, several decentralized sparse adaptive algorithms have been proposed recently. Most of them is focused on the single task estimation problems, in which all nodes receive data associated with the same unknown vector and collaborate to estimate it. However, many applications are inherently multitask oriented and each node has its own unknown vector different from others. The related multitask estimation problem benefits from collaborations among the nodes as neighbor nodes usually share analogous properties and thus similar unknown vectors. In this paper, we study the distributed sparse multitask recursive least squares (RLS) problem over networks. We first propose a decentralized online alternating direction method of multipliers algorithm for the formulated RLS problem. The algorithm is simplified for easy implementation with closed-form computations in each iteration and low storage requirements. Convergence analysis of the algorithm is presented. Moreover, to further reduce the complexity, we propose a decentralized online subgradient method with low computational overhead. We theoretically establish its mean square stability by providing upper bounds for the mean square deviation and the excess mean square error. A related distributed online proximal gradient method is presented and extension to clustered multitask networks is also provided. The effectiveness of the proposed algorithms is corroborated by numerical simulations and an accuracy-complexity tradeoff between the proposed algorithms is highlighted. [ABSTRACT FROM PUBLISHER]

We study the problem of designing transmit beamformers for a multigroup multicasting by considering a multiple-input single-output orthogonal frequency-division multiplexing framework. The design objective involves either minimizing the total transmit power for certain guaranteed quality of service or maximizing the minimum achievable rate among the users for a given transmit power budget. The problem of interest can be formulated as a nonconvex quadratically constrained quadratic programming (QCQP) for which the prevailing semidefinite relaxation (SDR) technique is inefficient for at least two reasons. At first, the relaxed problem cannot be reformulated as a semidefinite programming. Second, even if the relaxed problem is solved, the so-called randomization procedure should be used to generate a feasible solution to the original QCQP, which is difficult to derive for the considered problem. To overcome these shortcomings, we adopt successive convex approximation framework to find multicast beamformers directly. The proposed method not only avoids the need of randomization search, but also incurs less computational complexity compared to an SDR approach. In addition, we also extend multicasting beamformer design problem with an additional constraint on the number of active elements, which is particularly relevant when the number of antennas is larger than that of radio frequency chains. Numerical results are used to demonstrate the superior performance of our proposed methods over the existing solutions. [ABSTRACT FROM PUBLISHER]

In this paper, we present and analyze the performance of multidimensional ESPRIT ( $N$-D ESPRIT) method for estimating parameters of $N$-D superimposed damped and/or undamped exponentials. $N$-D ESPRIT algorithm is based on low-rank decomposition of multilevel Hankel matrices formed by the $N$ -D data. In order to reduce the computational complexity for large signals, we propose a fast $N$-D ESPRIT using truncated singular value decomposition (SVD). Then, through a first-order perturbation analysis, we derive simple expressions of the variance of the estimates in $N$-D multiple-tones case. These expressions do not involve the factors of the SVD. We also derive closed-form expressions of the variances of the complex modes, frequencies, and damping factors estimates in the $N$-D single-tone case. Computer results are presented to show effectiveness of the fast version of $N$-D ESPRIT and verify theoretical expressions. [ABSTRACT FROM PUBLISHER]

In this paper, we consider multiuser detection that copes with multiple access interference caused in low-rate wireless communication systems with a large number of nodes, such as machine-to-machine communications. We take account of discreteness of transmitted signals (e.g., binary signals taking values of $\pm 1$), which we utilize as prior information in detection. We first formulate the detection problem as a maximum a posteriori estimation problem. Since this problem is highly nonconvex and discontinuous, we propose convex relaxation based on the sum-of-absolute-values (SOAV) optimization, which can be efficiently solved by proximal splitting. We also derive an upper bound of the relaxation error by the SOAV optimization in noisy cases based on the restricted isometry property. Numerical simulations are shown to illustrate the effectiveness of the proposed approach. [ABSTRACT FROM PUBLISHER]

Sparse fast Fourier transform (FFT) is a promising technique that can significantly reduce computational complexity. However, only a handful of research has been conducted on precisely analyzing the performance of this new scheme. Accurate theoretical results are important for new techniques to avoid numerous simulations when applying them in various applications. In this study, we analyze several performance metrics and derive the corresponding closed-form expressions for the sparse FFT including 1) inter sparse interference due to nonideal windowing effects, 2) the probability of sparse elements overlapping, and 3) the recovering rate performance. From the analytical results, we gain insights and propose a novel mode-mean estimation algorithm for improving the performance. Simulation results are provided to show the accuracy of the derived results as well as the performance enhancement. We also show how to determine parameters to achieve the lowest computational complexity using these theoretical results. [ABSTRACT FROM PUBLISHER]

This paper addresses the issue of two-dimensional (2-D) direction of arrival (DOA) estimation with coprime planar arrays (CPPAs) via sparse representation. Our work differs from the partial spectral search approach [25], which suppresses the phase ambiguity by searching the common peaks of two subarrays. We focus on the coprime property of CPPA, where the sparse array extension model with sum–difference coarray (SDCA) is derived for larger degrees of freedom (DOFs). Besides, to optimize the selection of regularization parameter, we also construct a new sparse representation algorithm by estimating the errors between the signal and noise parts. Further, an iterative scheme is presented to transform the 2-D grids searching to several times of 1-D searching, where the initial values are obtained by extracting one difference coarray from SDCA. So the proposed method can achieve aperture extension, high estimation performance, and low computational complexity. Besides, the sparse array extension model for multiple-input multiple-output radars is discussed and the Cramér–Rao bound for 2-D DOA estimation with CPPA is also derived in detail. Finally, simulation results demonstrate the effectiveness of proposed method compared to the state-of-the-art methods. [ABSTRACT FROM PUBLISHER]

In multiple-input multiple-output radar, to localize a target and estimate its reflection coefficient, a given cost function is usually optimized over a grid of points. The performance of such algorithms is directly affected by the grid resolution. Increasing the number of grid points enhances the resolution of the estimator but also increases its computational complexity exponentially. In this paper, two reduced complexity algorithms are derived based on Capon and amplitude and phase estimation (APES) to estimate the reflection coefficient, angular location, and Doppler shift of multiple moving targets. By exploiting the structure of the terms, the cost function is brought into a form that allows us to apply the two-dimensional fast Fourier transform (2D-FFT) and reduce the computational complexity of estimation. Using low resolution 2D-FFT, the proposed algorithm identifies suboptimal estimates and feeds them as initial points to the derived Newton gradient algorithm. In contrast to the grid-based search algorithms, the proposed algorithm can optimally estimate on- and off-the-grid targets in very low computational complexity. A new APES cost function with better estimation performance is also discussed. Generalized expressions of the Cramér–Rao lower bound are derived to assess the performance of the proposed algorithm. [ABSTRACT FROM PUBLISHER]

We present a novel Wiener smoothing filter procedure for pilot-symbol-assisted estimation of oscillator phase noise. The procedure consists of forward and backward first-order infinite impulse response filtering the pilot symbols and combining the filter outputs to generate an estimate of the phase noise. We analyze the mean-square-error performance of this pilot-symbol-assisted forward–backward Wiener smoothing filter (FBWSF) procedure and show its optimality under the assumption that the phase noise is modeled as a first-order autoregressive moving average process. We then apply the FBWSF as a code-aided phase noise compensation technique in an iterative receiver framework. The iterative receiver presented here first estimates phase noise roughly by using the pilot-symbol-assisted FBWSF; then, it refines the estimates with the code-aided version of FBWSF. The resulting receiver achieves excellent error performance at a feasible level of computational complexity. [ABSTRACT FROM PUBLISHER]

In this paper, we develop a new method for the fast and memory-efficient computation of Slepian functions on the sphere. Slepian functions, which arise as the solution of the Slepian concentration problem on the sphere, have desirable properties for applications where measurements are only available within a spatially limited region on the sphere and/or a function is required to be analyzed over the spatially limited region. Slepian functions are currently not easily computed for large band-limits for an arbitrary spatial region due to high computational and large memory storage requirements. For the special case of a polar cap, the symmetry of the region enables the decomposition of the Slepian concentration problem into smaller subproblems and consequently the efficient computation of Slepian functions for large band-limits. By exploiting the efficient computation of Slepian functions for the polar cap region on the sphere, we develop a formulation, supported by a fast algorithm, for the approximate computation of Slepian functions for an arbitrary spatial region to enable the analysis of modern datasets that support large band-limits. For the proposed algorithm, we carry out accuracy analysis of the approximation, computational complexity analysis, and review of memory storage requirements. We illustrate, through numerical experiments, that the proposed method enables faster computation, and has smaller storage requirements, while allowing for sufficiently accurate computation of the Slepian functions. [ABSTRACT FROM PUBLISHER]

Given a dataset, the task of learning a transform that allows sparse representations of the data bears the name of dictionary learning. In many applications, these learned dictionaries represent the data much better than the static well-known transforms (Fourier, Hadamard etc.). The main downside of learned transforms is that they lack structure and, therefore, they are not computationally efficient, unlike their classical counterparts. These posse several difficulties especially when using power limited hardware such as mobile devices, therefore, discouraging the application of sparsity techniques in such scenarios. In this paper, we construct orthogonal and nonorthogonal dictionaries that are factorized as a product of a few basic transformations. In the orthogonal case, we solve exactly the dictionary update problem for one basic transformation, which can be viewed as a generalized Givens rotation, and then propose to construct orthogonal dictionaries that are a product of these transformations, guaranteeing their fast manipulation. We also propose a method to construct fast square but nonorthogonal dictionaries that are factorized as a product of few transforms that can be viewed as a further generalization of Givens rotations to the nonorthogonal setting. We show how the proposed transforms can balance very well data representation performance and computational complexity. We also compare with classical fast and learned general and orthogonal transforms. [ABSTRACT FROM PUBLISHER]

Based on the minimum noise subspace (MNS) method previously introduced in the context of blind channel identification, generalized minimum noise subspace (GMNS) is proposed in this paper for array processing that generalizes MNS with respect to the availability of only a fixed number of parallel computing units. Different batch and adaptive algorithms are then introduced for fast and parallel computation of signal (principal) and noise (minor) subspaces. The computational complexity of GMNS and its related estimation accuracy are investigated by simulated experiments and a real-life experiment in radio astronomy. It is shown that GMNS represents an excellent tradeoff between the computational gain and the subspace estimation accuracy, as compared to several standard subspace methods. [ABSTRACT FROM PUBLISHER]

Source localization based on signal strength measurements has become very popular due to its practical simplicity. However, the severe nonlinearity and non-convexity make the related optimization problem mathematically difficult to solve, especially when the transmit power or the path-loss exponent (PLE) is unknown. Moreover, even if the PLE is known but not perfectly estimated or the anchor location information is not accurate, the constructed data model will become uncertain, making the problem again hard to solve. This paper particularly focuses on differential received signal strength (DRSS)-based localization with model uncertainties in case of unknown transmit power and PLE. A new whitened model for DRSS-based localization with unknown transmit powers is first presented and investigated. When assuming the PLE is known, we introduce two estimators based on an exact data model, an advanced best linear unbiased estimator (A-BLUE) and a Lagrangian estimator (LE), and then we present a robust semidefinite programming (SDP)-based estimator (RSDPE), which can cope with model uncertainties (imperfect PLE and inaccurate anchor location information). The three proposed estimators have their own advantages from different perspectives: the A-BLUE has the lowest complexity; the LE holds the best accuracy for a small measurement noise; and the RSDPE yields the best performance under a large measurement noise and possesses a very good robustness against model uncertainties. Finally, we propose a robust SDP-based block coordinate descent estimator (RSDP-BCDE) to deal with a completely unknown PLE and its performance converges to that of the RSDPE using a perfectly known PLE. [ABSTRACT FROM PUBLISHER]

This paper concerns the sparse Bayesian learning (SBL) problem for group sparse signals. Group sparsity means that the signal coefficients can be divided into groups and that the entries in one group are simultaneously zero or nonzero. In SBL, each group is controlled by a hyperparameter, which is estimated by solving the marginal likelihood maximization (MLM) problem. MLM is used to maximize the marginal likelihood of a given hyper-parameter by fixing all others. The main contribution of this paper is to extend the fast marginal likelihood maximization (FMLM) method to the group sparsity case. The key process of realizing FMLM in the group sparsity case is solved by finding the roots of a polynomial. Hence, the local maximum of the marginal likelihood can be found exactly, and the final estimation is obtained more efficiently. Furthermore, most large matrix inverses involved in MLM are replaced with the eigenvalue decompositions of much smaller matrices, which substantially reduces the computational complexity. Numerical results with both simulated and real data demonstrate the excellent performance and relatively high computational efficiency of the proposed method. [ABSTRACT FROM PUBLISHER]

Particle filters are broadly used to approximate posterior distributions of hidden states in state-space models by means of sets of weighted particles. While the convergence of the filter is guaranteed when the number of particles tends to infinity, the quality of the approximation is usually unknown but strongly dependent on the number of particles. In this paper, we propose a novel method for assessing the convergence of particle filters in an online manner, as well as a simple scheme for the online adaptation of the number of particles based on the convergence assessment. The method is based on a sequential comparison between the actual observations and their predictive probability distributions approximated by the filter. We provide a rigorous theoretical analysis of the proposed methodology and, as an example of its practical use, we present simulations of a simple algorithm for the dynamic and online adaptation of the number of particles during the operation of a particle filter on a stochastic version of the Lorenz 63 system. [ABSTRACT FROM PUBLISHER]

This paper explores and analyzes two randomized designs for robust principal component analysis employing low-dimensional data sketching. In one design, a data sketch is constructed using random column sampling followed by low-dimensional embedding, while in the other, sketching is based on random column and row sampling. Both designs are shown to bring about substantial savings in complexity and memory requirements for robust subspace learning over conventional approaches that use the full scale data. A characterization of the sample and computational complexity of both designs is derived in the context of two distinct outlier models, namely, sparse and independent outlier models. The proposed randomized approach can provably recover the correct subspace with computational and sample complexity which depend only weakly on the size of the data (only through the coherence parameters). The results of the mathematical analysis are confirmed through numerical simulations using both synthetic and real data. [ABSTRACT FROM PUBLISHER]

A rigorous formulation of the dynamics of a signal processing scheme aimed at dense signal scanning without any loss in accuracy is introduced and analyzed. Related methods proposed in the recent past lack a satisfactory analysis of whether they actually fulfill any exactness constraints. This is improved through an exact characterization of the requirements for a sound sliding window approach. The tools developed in this paper are especially beneficial if Convolutional Neural Networks are employed, but can also be used as a more general framework to validate related approaches to signal scanning. The proposed theory helps to eliminate redundant computations and renders special case treatment unnecessary, resulting in a dramatic boost in efficiency particularly on massively parallel processors. This is demonstrated both theoretically in a computational complexity analysis and empirically on modern parallel processors. [ABSTRACT FROM PUBLISHER]

The Rao test is an important method in signal detection in the presence of unknown parameters. The traditional approach to the problem when the unknown parameters are complex valued is to form a corresponding real-valued parameter vector and then to use the real Rao test. Alternatively, we present a complex parameter Rao test by reformulating the calculations with respect to the complex-valued quantities directly. Two important examples of the application of the complex parameter Rao test are given to illustrate the procedure. [ABSTRACT FROM PUBLISHER]

Dictionary learning is the task of determining a data-dependent transform that yields a sparse representation of some observed data. The dictionary learning problem is nonconvex, and usually solved via computationally complex iterative algorithms. Furthermore, the resulting transforms obtained generally lack structure that permits their fast application to data. To address this issue, this paper develops a framework for learning orthonormal dictionaries, which are built from products of a few Householder reflectors. Two algorithms are proposed to learn the reflector coefficients: one that considers a sequential update of the reflectors and one with a simultaneous update of all reflectors that imposes an additional internal orthogonal constraint. The proposed methods have low computational complexity and are shown to converge to local minimum points, which can be described in terms of the spectral properties of the matrices involved. The resulting dictionaries balance between the computational complexity and the quality of the sparse representations by controlling the number of householder reflectors in their product. Simulations of the proposed algorithms are shown in the image processing setting, where well-known fast transforms are available for comparisons. The proposed algorithms have favorable reconstruction error and the advantage of a fast implementation relative to the classical, unstructured dictionaries. [ABSTRACT FROM PUBLISHER]

Hybrid beamforming, which consists of an RF precoder and a baseband precoder, has been proposed to reduce the number of RF chains at the massive multiple input multiple output (MIMO) base station (BS). This paper studies the impact of channel state information (CSI) on the capacity of massive MIMO systems with codebook-based hybrid beamforming , where the RF precoder is selected from a finite size codebook. Two types of CSI at the BS (CSIT) are commonly assumed: full instantaneous CSIT and hybrid CSIT (channel statistics plus the low-dimensional effective channel matrix). With full instantaneous CSIT, both the RF and baseband precoders are adaptive to the full instantaneous CSI at the fast timescale. With hybrid CSIT, the RF precoder is adaptive to channel statistics only, and the baseband precoder is adaptive to the instantaneous effective channel, yielding lower implementation complexity by sacrificing some capacity. We derive asymptotic sum capacity expressions under these two types of CSIT. We find that, in codebook-based hybrid beamforming systems, exploiting the full instantaneous CSIT can only achieve a marginal SNR gain and hybrid CSIT is sufficient to achieve the first-order gain provided by the massive MIMO for most of the cases. We also propose fast and slow timescale RF precoding algorithms, which asymptotically achieve the capacity under full instantaneous CSIT and hybrid CSIT, respectively. [ABSTRACT FROM PUBLISHER]

Distributed radar systems are capable of enhancing the detection performance by using multiple widely spaced distributed antennas. With prior statistic information of targets, resource allocation is of critical importance for further improving the system's achievable performance. In this paper, the total transmitted power is minimized at a given mean-square target-estimation error. We derive two iterative decomposition algorithms for solving this nonconvex constrained optimization problem, namely, the optimality condition decomposition (OCD)-based and the alternating direction method of multipliers (ADMM)-based algorithms. Both the convergence performance and the computational complexity of our algorithms are analyzed theoretically, which are then confirmed by our simulation results. The OCD method imposes a much lower computational burden per iteration, while the ADMM method exhibits a higher per-iteration complexity, but as a benefit of its significantly faster convergence speed, it requires less iterations. Therefore, the ADMM imposes a lower total complexity than the OCD. The results also show that both of our schemes outperform the state-of-the-art benchmark scheme for the multiple-target case, in terms of the total power allocated, at the cost of some degradation in localization accuracy. For the single-target case, all the three algorithms achieve similar performance. Our ADMM algorithm has similar total computational complexity per iteration and convergence speed to those of the benchmark. [ABSTRACT FROM PUBLISHER]

In this paper, the method of splitting or parallelization of calculation of the $N$-point discrete Fourier transform (DFT) by the DFTs of smaller orders is described. For that the concept of partitions revealing the one-dimensional (1-D) DFT of order $q2^r,$ where $r > 1$ and $q > 1$ is a positive odd number, is described. Two different partitions are considered and the corresponding effective algorithms of calculation of the $q2^r$ -point 1-D DFT are described for the $q=3$ case. The calculation of the transform is based on the paired representations, when the signal is represented as a set of 1-D signals which define the 1-D DFT in disjoint subsets of frequency-points which cover the set of all frequencies. The splittings of the $q2^r$ -point 1-D DFT are performed by the 1-D discrete 2- and $q$ -paired transforms which allow for calculating with a minimum number of operations. The examples of the paired transforms and computational complexity of the proposed algorithms for the $N=6$ and 12 cases are given. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a strategy that is based on expectation maximization for tracking multiple point targets. The algorithm is similar to probabilistic multi-hypothesis tracking (PMHT) but does not relax the point target model assumptions. According to the point target models, a target can generate at most one measurement, and a measurement is generated by at most one target. With this model assumption, we show that the proposed algorithm can be implemented as iterations of Rauch-Tung-Striebel (RTS) smoothing for state estimation, and the loopy belief propagation method for marginal data association probabilities calculation. Using example illustrations with tracks, we compare the proposed algorithm with PMHT and joint probabilistic data association (JPDA) and show that PMHT and JPDA exhibit coalescence when there are closely moving targets whereas the proposed algorithm does not. Furthermore, extensive simulations c comparing the mean optimal subpattern assignment (MOSPA) performance of the algorithm for different scenarios averaged over several Monte Carlo iterations show that the proposed algorithm performs better than JPDA and PMHT. We also compare it to benchmarking algorithm: $N$-scan pruning based track-oriented multiple hypothesis tracking (TOMHT). The proposed algorithm shows a good tradeoff between computational complexity and the MOSPA performance. [ABSTRACT FROM PUBLISHER]

In compressed sensing the matrices that satisfy the Restricted Isometry Property (RIP) play an important role. To date, however, very few results for designing such matrices are available. For applications such as multiplier-less data compression, binary sensing matrices are of interest. The present paper constructs deterministic and binary sensing matrices using Euler Squares. In particular, given a positive integer m different from p,{p}^{2} for a prime p , we show that it is possible to construct a binary sensing matrix of size mtimes c(mmu)^2, where mu is the coherence parameter of the matrix and $cin [1,2)$. The matrices that we construct have small density (that is, percentage of nonzero entries in the matrix is small) with no function evaluation in their construction, which support algorithms with low computational complexity. Through experimental work, we show that our binary sensing matrices can be used for such applications as content based image retrieval. Our simulation results demonstrate that the Euler Square based CS matrices give better performance than their Gaussian counterparts. [ABSTRACT FROM AUTHOR]

This paper studies the joint user association and resource allocation in heterogeneous networks (HetNets) from a novel perspective, motivated by and generalizing the idea of fractional frequency reuse. By treating the multi-cell multi-user resource allocation as resource partitioning among multiple reuse patterns, we propose a unified framework to analyze and compare a wide range of user association and resource allocation strategies for HetNets, and provide an optimal benchmark for network performance. The enabling mechanisms are a novel formulation to consider all possible interference patterns or any pre-defined subset of patterns, and efficient sparsity-pursuit algorithms to find the solution. A notable feature of this formulation is that the patterns remain fixed during the resource optimization process. This creates a favorable opportunity for convex formulations while still considering interference coupling. More important, in view of the fact that multi-cell resource allocation is very computational demanding, our framework provides a systematic way to trade off performance for the reduction of computational complexity by restricting the candidate patterns to a small number of feature patterns. Relying on the sparsity-pursuit capability of the proposed algorithms, we develop a practical guideline to identify the feature patterns. Numerical results show that the identified feature patterns can significantly improve the existing strategies, and jointly optimizing the user association and resource allocation indeed brings considerable gain. [ABSTRACT FROM AUTHOR]

We consider the problem of the selection of channel sensing order in cognitive radio networks (CRNs) where the primary users (PUs) use multiple channels for data transmission. We assume that the occupancy state of each channel is correlated with that of the other channels, and the spectrum occupancy state for all the channels follows the discrete-time Markov model. In this paper, we propose to characterize the channel availability of the primary network using the idle probability of consecutive time slots (IPCOTS). Under the discrete-time Markov model, we derive the IPCOTS of each particular channel, under the condition that the states of all the channels in the primary network are identically distributed. Moreover, we propose a suboptimal state-dependent policy, called IPCOTS policy, for the selection of channel sensing order. Finally, we extend the policy to three typical cases. Simulation results show that, in an M/M/m/m-modeled primary network, more secondary user (SU) rewards can be obtained using the IPCOTS policy in comparison with the existing approaches. [ABSTRACT FROM PUBLISHER]

This paper considers the coherent integration problem for maneuvering target detection and motion parameters estimation, involving range migration (RM) and Doppler frequency migration (DFM) within the coherent pulse interval. A fast non-searching method based on adjacent cross correlation function (ACCF) and Lv’s distribution (LVD) is proposed, where the adjacent correlation operation is first employed to remove the RM and reduce the order of DFM. After that, LVD is applied to realize the coherent integration, target detection and parameters estimation. In addition, at the cost of some performance loss, another fast method via ACCF iteratively is also introduced to further reduce the computational complexity and obtain the motion parameters estimation. The proposed two methods are fast in that they can be easily implemented by using complex multiplications, the fast Fourier transform (FFT) and inverse FFT (IFFT). Compared with the existing methods, the presented algorithms can obtain the motion parameters estimation without any searching procedure and can achieve a good balance between the computational cost and the detection ability as well as parameters estimation performance. Finally, several simulation experiments are provided to demonstrate the effectiveness. [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]

This paper develops power control algorithms for energy efficiency (EE) maximization (measured in bit/Joule) in wireless networks. Unlike previous related works, minimum-rate constraints are imposed and the signal-to-interference-plus-noise ratio takes a more general expression, which allows one to encompass some of the most promising 5G candidate technologies. Both network-centric and user-centric EE maximizations are considered. In the network-centric scenario, the maximization of the global EE and the minimum EE of the network is performed. Unlike previous contributions, we develop centralized algorithms that are guaranteed to converge, with affordable computational complexity, to a Karush–Kuhn–Tucker point of the considered non-convex optimization problems. Moreover, closed-form feasibility conditions are derived. In the user-centric scenario, game theory is used to study the equilibria of the network and to derive convergent power control algorithms, which can be implemented in a fully decentralized fashion. Both scenarios above are studied under the assumption that single or multiple resource blocks are employed for data transmission. Numerical results assess the performance of the proposed solutions, analyzing the impact of minimum-rate constraints, and comparing the network-centric and user-centric approaches. [ABSTRACT FROM AUTHOR]

In this paper, a discrete LCT (DLCT) irrelevant to the sampling periods and without oversampling operation is developed. This DLCT is based on the well-known CM-CC-CM decomposition, that is, implemented by two discrete chirp multiplications (CMs) and one discrete chirp convolution (CC). This decomposition doesn’t use any scaling operation which will change the sampling period or cause the interpolation error. Compared with previous works, DLCT calculated by direct summation and DLCT based on center discrete dilated Hermite functions (CDDHFs), the proposed method implemented by FFTs has much lower computational complexity. The relation between the proposed DLCT and the continuous LCT is also derived to approximate the samples of the continuous LCT. Simulation results show that the proposed method somewhat outperforms the CDDHFs-based method in the approximation accuracy. Besides, the proposed method has approximate additivity property with error as small as the CDDHFs-based method. Most importantly, the proposed method has perfect reversibility, which doesn’t hold in many existing DLCTs. With this property, it is unnecessary to develop the inverse DLCT additionally because it can be replaced by the forward DLCT. [ABSTRACT FROM AUTHOR]