Search

In this paper, we propose an algorithm to design interference alignment (IA) precoding and decoding matrices for arbitrary MIMO X networks. The proposed algorithm is rooted in the homotopy continuation techniques commonly used to solve systems of nonlinear equations. Homotopy methods find the solution of a target system by smoothly deforming the solution of a start system which can be trivially solved. Unlike previously proposed IA algorithms, the homotopy continuation technique allows us to solve the IA problem for both unstructured (i.e., generic) and structured channels such as those that arise when time or frequency symbol extensions are jointly employed with the spatial dimension. To this end, we consider an extended system of bilinear equations that include the standard alignment equations to cancel the interference, and a new set of bilinear equations that preserve the desired dimensionality of the signal spaces at the intended receivers. We propose a simple method to obtain the start system by randomly choosing a set of precoders and decoders, and then finding a set of channels satisfying the system equations, which is a linear problem. Once the start system is available, standard prediction and correction techniques are applied to track the solution all the way to the target system. We analyze the convergence of the proposed algorithm and prove that, for many feasible systems and a sufficiently small continuation parameter, the algorithm converges with probability one to a perfect IA solution. The simulation results show that the proposed algorithm is able to consistently find solutions achieving the maximum number of degrees of freedom in a variety of MIMO X networks with or without symbol extensions. Further, the algorithm provides insights into the feasibility of IA in MIMO X networks for which theoretical results are scarce. [ABSTRACT FROM PUBLISHER]

In this paper, we present a novel approach for achieving phase desynchronization in a pulse-coupled oscillator network. Ensuring phase desynchronization is a difficult problem, and existing results are constrained to a completely interconnected network and a fixed number of nodes. Our approach is more robust than previous approaches, removing the constraint of a fixed number of nodes. The removal of this constraint is significant because it allows the network to receive and drop nodes freely without any change to the phase update strategy. Also, to our knowledge, our approach is the first to prove the convergence to the desynchronized state for a topology that is more general than the all-to-all topology. More specifically, our approach is applicable to any circulant, symmetric network topology, including the circulant symmetric ring topology. Rigorous mathematical proofs are provided to support the result that any circulant, symmetric network with ordered phases under our proposed algorithm will converge to uniform phase desynchronization. Simulation results are also presented to demonstrate the algorithm's performance. [ABSTRACT FROM PUBLISHER]

The performance of full-duplex (FD) relay systems can be greatly impacted by the self-interference (SI) at relays. By exploiting multiple antennas, the spectral efficiency of FD relay systems can be enhanced through spatial SI mitigation. This paper studies joint source transmit beamforming and relay processing to achieve rate maximization for FD multiple-input–multiple-output (MIMO) amplify-and-forward (AF) relay systems with consideration of relay processing delay. The problem is difficult to solve mainly due to the SI constraint induced by the relay processing delay. In this paper, we first present a sufficient condition under which the relay amplification matrix has rank-one structure. Then, for the case of rank-one amplification matrix, the rate maximization problem is equivalently simplified into an unconstrained problem that can be locally solved using the gradient ascent method. Next, we propose a penalty-based algorithmic framework, named P-BSUM, for a class of constrained optimization problems that have difficult equality constraints in addition to some convex constraints. By rewriting the rate maximization problem with a set of auxiliary variables, we apply the P-BSUM algorithm to the rate maximization problem in the general case. Finally, numerical results validate the efficiency of the proposed algorithms and show that the joint source-relay design approach under the rank-one assumption could be strictly suboptimal as compared to the P-BSUM-based joint source-relay design approach. [ABSTRACT FROM PUBLISHER]

Recently, several high-resolution parameter estimation algorithms have been developed to exploit the structure of strictly second-order (SO) non-circular (NC) signals. They achieve a higher estimation accuracy and can resolve up to twice as many signal sources compared to the traditional methods for arbitrary signals. As a benchmark for these NC methods, we derive the closed-form deterministic $R$ -D NC Cramér-Rao bound (NC CRB) for the multi-dimensional parameter estimation of strictly non-circular (rectilinear) signal sources in this paper. Assuming a separable centro-symmetric $R$-D array, we show that in some special cases, the deterministic $R$-D NC CRB reduces to the existing deterministic $R$-D CRB for arbitrary signals. This suggests that no gain from strictly non-circular sources (NC gain) can be achieved under the deterministic data assumption in these cases. For more general scenarios, finding an analytical expression of the NC gain for an arbitrary number of sources is very challenging. Thus, in this paper, we simplify the derived NC CRB and the existing CRB for the special case of two closely-spaced strictly non-circular sources captured by a uniform linear array (ULA). Subsequently, we use these simplified CRB expressions to analytically compute the maximum achievable asymptotic NC gain for the considered two source case. The resulting expression only depends on the various physical parameters and we find the conditions that provide the largest NC gain. Our analysis is supported by extensive simulation results. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of robustly estimating a structured covariance matrix with an elliptical underlying distribution with a known mean. In applications where the covariance matrix naturally possesses a certain structure, taking the prior structure information into account in the estimation procedure is beneficial to improving the estimation accuracy. We propose incorporating the prior structure information into Tyler's M-estimator and formulating the problem as minimizing the cost function of Tyler's estimator under the prior structural constraint. First, the estimation under a general convex structural constraint is introduced with an efficient algorithm for finding the estimator derived based on the majorization-minimization (MM) algorithm framework. Then, the algorithm is tailored to several special structures that enjoy a wide range of applications in signal processing related fields, namely, sum of rank-one matrices, Toeplitz, and banded Toeplitz structure. In addition, two types of non-convex structures, i.e., the Kronecker structure and the spiked covariance structure, are also discussed, where it is shown that simple algorithms can be derived under the guidelines of MM. The algorithms are guaranteed to converge to a stationary point of the problems. Furthermore, if the constraint set is geodesically convex, such as the Kronecker structure set, then the algorithm converges to a global minimum. Numerical results show that the proposed estimator achieves a smaller estimation error than the benchmark estimators at a lower computational cost. [ABSTRACT FROM AUTHOR]

This work addresses the problem of learning sparse representations of tensor data using structured dictionary learning. It proposes learning a mixture of separable dictionaries to better capture the structure of tensor data by generalizing the separable dictionary learning model. Two different approaches for learning mixture of separable dictionaries are explored and sufficient conditions for local identifiability of the underlying dictionary are derived in each case. Moreover, computational algorithms are developed to solve the problem of learning mixture of separable dictionaries in both batch and online settings. Numerical experiments are used to show the usefulness of the proposed model and the efficacy of the developed algorithms. [ABSTRACT FROM AUTHOR]

We consider a class of popular distributed non-convex optimization problems, in which agents connected by a network $\mathcal {G}$ collectively optimize a sum of smooth (possibly non-convex) local objective functions. We address the following question: if the agents can only access the gradients of local functions, what are the fastest rates that any distributed algorithms can achieve, and how to achieve those rates. First, we show that there exist difficult problem instances, such that it takes a class of distributed first-order methods at least $\mathcal {O}(1/\sqrt{\xi ({ \mathcal {G} })} \times \bar{L} /{\epsilon })$ communication rounds to achieve certain $\epsilon$ -solution [where $\xi ({ \mathcal {G} })$ denotes the spectral gap of the graph Laplacian matrix, and $\bar{L}$ is some Lipschitz constant]. Second, we propose (near) optimal methods whose rates match the developed lower rate bound (up to a ploylog factor). The key in the algorithm design is to properly embed the classical polynomial filtering techniques into modern first-order algorithms. To the best of our knowledge, this is the first time that lower rate bounds and optimal methods have been developed for distributed non-convex optimization problems. [ABSTRACT FROM AUTHOR]

In this paper we present a generic framework for the asymptotic performance analysis of subspace-based parameter estimation schemes. It is based on earlier results on an explicit first-order expansion of the estimation error in the signal subspace obtained via an SVD of the noisy observation matrix. We extend these results in a number of aspects. Firstly, we demonstrate that an explicit first-order expansion of the Higher-Order SVD (HOSVD)-based subspace estimate can be derived. Secondly, we show how to obtain explicit first-order expansions of the estimation error of arbitrary ESPRIT-type algorithms and provide the expressions for R-D Standard ESPRIT, R-D Unitary ESPRIT, R-D Standard Tensor-ESPRIT, as well as R-D Unitary Tensor-ESPRIT. Thirdly, we derive closed-form expressions for the mean square error (MSE) and show that they only depend on the second-order moments of the noise. Hence, to apply this framework we only need the noise to be zero mean and possess finite second order moments. Additional assumptions such as Gaussianity or circular symmetry are not needed. [ABSTRACT FROM PUBLISHER]

Distributed estimation of the average value over a Wireless Sensor Network has recently received a lot of attention. Most papers consider single variable sensors and communications with feedback (e.g., peer-to-peer communications). However, in order to use efficiently the broadcast nature of the wireless channel, communications without feedback are advocated. To ensure the convergence in this feedback-free case, the recently-introduced Sum-Weight-like algorithms which rely on two variables at each sensor are a promising solution. In this paper, the convergence towards the consensus over the average of the initial values is analyzed in depth. Furthermore, it is shown that the squared error decreases exponentially with the time. In addition, a powerful algorithm relying on the Sum-Weight structure and taking into account the broadcast nature of the channel is proposed. [ABSTRACT FROM PUBLISHER]

Passive source localization is one of the issues in array signal processing fields. In some practical applications, the signals received by an array are the mixture of near-field and far-field sources, such as speaker localization using microphone arrays and guidance (homing) systems. To localize mixed near-field and far-field sources, this paper develops a two-stage MUSIC algorithm using cumulant. The key points of this paper are: i) in the first stage, this paper derives one special cumulant matrix, in which the virtual "steering vector" is the function of the common electric angle in both near-field and far-field signal models so that source direction-of-arrival (DOA) (near-field or far-field one) can be obtained from this electric angle using the conventional high-resolution MUSIC algorithm; ii) in the second stage, this paper derives another particular cumulant matrix, in which the virtual "steering matrix" has full column rank no matter whether the received signals are multiple near-field sources or multiple far-field ones or their mixture. What is more important, the virtual "steering vector" can be separated into two parts, in which the first one is the function of the common electric angle in both signal models, whereas the second part is the function of the electric angle that exists only in near-field signal model. Furthermore, by substituting the common electric angle estimated in the first stage into one special Hermitian matrix formed from another MUSIC spectral function, the range of near-field sources can be obtained from the eigenvector of the Hermitian matrix. The resultant algorithm avoids twodimensional search and pairing parameters; in addition, it avoids the estimation failure problem and alleviates aperture loss. Simulation results are presented to validate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

This paper introduces the graph-structured recursive least squares (GS-RLS) algorithm, which is a very efficient means to track a linear time-varying system when the inputs to the system have structure that can be modeled using a decomposable Gaussian graphical model. For graphs with small clique sizes, it is shown that GS-RLS can achieve tracking performance very close to that of the conventional RLS algorithm for a fraction of the computational cost. In particular, after proving that the outputs of wide-sense stationary time-varying communication channels have graphical model structure if the inputs are cyclostationary, significant computational gains are realized for adaptive equalization of the time-varying underwater acoustic communication channel using the GS-RLS algorithm. This is verified using field data from the SPACE08 underwater acoustic communication experiment. [ABSTRACT FROM AUTHOR]

One-bit quantization can significantly reduce the massive multiple-input and multiple-output (MIMO) system hardware complexity, but at the same time it also brings great challenges to the system algorithm design. Specifically, it is difficult to recover information from the highly distorted samples as well as to obtain accurate channel estimation without increasing the number of pilots. In this paper, a novel inference algorithm called variational approximate message passing (VAMP) for one-bit quantized massive MIMO receiver is developed, which attempts to exploit the advantages of both the variational Bayesian inference algorithm and the bilinear generalized approximated message passing algorithm to accomplish joint channel estimation and data detection in a closed form with first-order complexity. Asymptotic state evolution analysis indicates the fast convergence rate of VAMP and also provides a lower bound for the data detection error. Moreover, through extensive simulations, we show that VAMP can achieve excellent detection performance with low pilot overhead in a wide range of scenarios. [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]

In this paper, we present new algorithms and analysis for the linear inverse sensor placement and scheduling problems over multiple time instances with power and communications constraints. The proposed algorithms, which deal directly with minimizing the mean squared error (MSE), are based on the convex relaxation approach to address the binary optimization scheduling problems that are formulated in sensor network scenarios. We propose to balance the energy and communications demands of operating a network of sensors over time while we still guarantee a minimum level of estimation accuracy. We measure this accuracy by the MSE for which we provide average case and lower bounds analyses that hold in general, irrespective of the scheduling algorithm used. We show experimentally how the proposed algorithms perform against state-of-the-art methods previously described in the literature. [ABSTRACT FROM AUTHOR]

In phase retrieval problems, a signal of interest (SOI) is reconstructed based on the magnitude of a linear transformation of the SOI observed with additive noise. The linear transform is typically referred to as a measurement matrix. Many works on phase retrieval assume that the measurement matrix is a random Gaussian matrix, which, in the noiseless scenario with sufficiently many measurements, guarantees invertability of the transformation between the SOI and the observations, up to an inherent phase ambiguity. However, in many practical applications, the measurement matrix corresponds to an underlying physical setup, and is therefore deterministic, possibly with structural constraints. In this paper, we study the design of deterministic measurement matrices, based on maximizing the mutual information between the SOI and the observations. We characterize necessary conditions for the optimality of a measurement matrix, and analytically obtain the optimal matrix in the low signal-to-noise ratio regime. Practical methods for designing general measurement matrices and masked Fourier measurements are proposed. Simulation tests demonstrate the performance gain achieved by the suggested techniques compared to random Gaussian measurements for various phase recovery algorithms. [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]

Index tracking is a popular passive portfolio management strategy that aims at constructing a portfolio that replicates or tracks the performance of a financial index. The tracking error can be minimized by purchasing all the assets of the index in appropriate amounts. However, to avoid small and illiquid positions and large transaction costs, it is desired that the tracking portfolio consists of a small number of assets, i.e., a sparse portfolio. The optimal asset selection and capital allocation can be formulated as a combinatorial problem. A commonly used approach is to use mixed-integer programming (MIP) to solve small sized problems. Nevertheless, MIP solvers can fail for high-dimensional problems while the running time can be prohibiting for practical use. In this paper, we propose efficient and fast index tracking algorithms that automatically perform asset selection and capital allocation under a set of general convex constraints. A special consideration is given to the case of the nonconvex holding constraints and to the downside risk tracking measure. Furthermore, we derive specialized algorithms with closed-form updates for particular sets of constraints. Numerical simulations show that the proposed algorithms match or outperform existing methods in terms of performance, while their running time is lower by many orders of magnitude. [ABSTRACT FROM PUBLISHER]

We consider the recovery of a continuous domain piecewise constant image from its nonuniform Fourier samples using a convex matrix completion algorithm. We assume the discontinuities/edges of the image are localized to the zero level set of a bandlimited function. This assumption induces linear dependencies between the Fourier coefficients of the image, which results in a two-fold block Toeplitz matrix constructed from the Fourier coefficients being low rank. The proposed algorithm reformulates the recovery of the unknown Fourier coefficients as a structured low-rank matrix completion problem, where the nuclear norm of the matrix is minimized subject to structure and data constraints. We show that the exact recovery is possible with high probability when the edge set of the image satisfies an incoherency property. We also show that the incoherency property is dependent on the geometry of the edge set curve, implying higher sampling burden for smaller curves. This paper generalizes recent work on the super-resolution recovery of isolated Diracs or signals with finite rate of innovation to the recovery of piecewise constant images. [ABSTRACT FROM AUTHOR]

Bounded component analysis (BCA) is a recently introduced approach including independent component analysis as a special case under the assumption of source boundedness. In this paper, we provide a stationary point analysis for the recently proposed instantaneous BCA algorithms that are capable of separating dependent, even correlated as well as independent sources from their mixtures. The stationary points are identified and characterized as either perfect separators, which are the global maxima of the proposed optimization scheme or saddle points. The important result emerging from the analysis is that there are no local optima that can prevent the proposed BCA algorithms from converging to perfect separators. [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]

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]

Detection of the number of transmit antennas plays an important role in the design of adaptive multiantenna wireless communication systems. This paper develops a detection algorithm based on second- and fourth-order statistics of the received signal and time-varying nature of the wireless channel. In contrast to existing feature-based algorithms, the proposed algorithm does not require a priori information about the transmitted signals, such as coding scheme, modulation type, and pilot patterns. Unlike information-theoretic algorithms, it does not require the number of receive antennas to be larger than that of transmit antennas. In fact, the proposed algorithm is capable of operating with a single receive antenna even for large numbers of transmit antennas. The performance analysis of the proposed algorithm is provided, and the results are verified through simulations. The algorithm exhibits a good performance over a wide range of signal-to-noise ratios, and is robust to the carrier frequency and timing offsets. [ABSTRACT FROM PUBLISHER]

The multiple-input multiple-output (MIMO) system makes efficient use of spectrum and increases the transmission throughput in wireless communications. The sphere decoding (SD) is an efficient algorithm that enables the maximum-likelihood (ML) detection for the MIMO system. However, the SD algorithm has variable complexity, and its complexity increases rapidly with decreasing signal-to-noise ratio (SNR). In this paper, we propose a novel ML detection algorithm for the MIMO system based on differential metrics. We define the differential metrics and derive the associated recursive calculation. We then give the indicative functions, which can be used to possibly find some ML-detected bits of the initial sequence. The indicative functions are further applied to implement an efficient tree search for ML detection. The proposed algorithm does not need QR decomposition and matrix inversion. The tree search process needs only the additive operation, while the number of multiplications before the tree search is constant. Our algorithm can achieve the exact ML detection as the SD algorithm. Unlike the SD algorithm, the complexity of our algorithm reduces with decreasing SNR, whereas at high SNR, the complexity is nearly constant. We also give the convergence analysis for the SD and proposed algorithms, and the simulation verifies our analysis. For the proposed algorithm, the number of necessary memory is constant during the tree search, and the implementation by parallel processing is possible. The soft output of ML-detected bits can also be generated in our algorithm. [ABSTRACT FROM PUBLISHER]

Partition-wise models offer a flexible approach for modeling complex and multidimensional data and are capable of producing interpretable results. They are based on partitioning the observed data into regions, each of which is modeled with a simple submodel. The success of this approach highly depends on the quality of the partition, as too large a region could lead to a nonsimple submodel, while too small a region could inflate estimation variance. This paper proposes an automatic procedure for choosing the partition (i.e., the number of regions and the boundaries between regions) as well as the submodels for the regions. It is shown that under the assumption of the existence of a true partition, as well as a set of known significant predictors, the proposed partition estimator is statistically consistent. Features of the proposed methodology are highlighted for both regression and classification problems on synthetic and real data. [ABSTRACT FROM PUBLISHER]

The problem of transmit code design in multiple-input multiple-output (MIMO) radar systems is addressed in this paper. The problem is considered in both colocated and widely separated antenna radars in the presence of signal-dependent interference and target mobility. Due to complexity of exact expressions of the optimal detector in the MIMO radars, information theoretic criteria are employed as design metrics which results in a general form of nonconvex optimization problems. In order to tackle the problem, a novel technique based on the minorization-maximization algorithm is proposed and solutions are presented under practical constraints on the transmit code, namely energy constraint, peak-to-average-power ratio constraint, and similarity constraint. Furthermore, the devised method is extended to be robust against uncertainties of the clutter and interference statistics. Finally, numerical examples are used to show the performance of the proposed technique in different situations. [ABSTRACT FROM PUBLISHER]

The success of compressed sensing relies essentially on the ability to efficiently find an approximately sparse solution to an under-determined linear system. In this paper, we developed an efficient algorithm for the sparsity promoting \ell^1-regularized least squares problem by coupling the primal dual active set strategy with a continuation technique (on the regularization parameter). In the active set strategy, we first determine the active set from primal and dual variables, and then update the primal and dual variables by solving a low-dimensional least square problem on the active set, which makes the algorithm very efficient. The continuation technique globalizes the convergence of the algorithm, with provable global convergence under restricted isometry property (RIP). Further, we adopt two alternative methods, i.e., a modified discrepancy principle and a Bayesian information criterion, to choose the regularization parameter automatically. Numerical experiments indicate that our algorithm is very competitive with state-of-the-art algorithms in terms of accuracy and efficiency, without a priori information about the regularization parameter. [ABSTRACT FROM AUTHOR]

In traditional compressed sensing theory, the dictionary matrix is given a priori, whereas in real applications this matrix suffers from random noise and fluctuations. In this paper, we consider a signal model where each column in the dictionary matrix is affected by a structured noise. This formulation is common in direction-of-arrival (DOA) estimation of off-grid targets, encountered in both radar systems and array processing. We propose to use joint sparse signal recovery to solve the compressed sensing problem with structured dictionary mismatches and also give an analytical performance bound on this joint sparse recovery. We show that, under mild conditions, the reconstruction error of the original sparse signal is bounded by both the sparsity and the noise level in the measurement model. Moreover, we implement fast first-order algorithms to speed up the computing process. Numerical examples demonstrate the good performance of the proposed algorithm and also show that the joint-sparse recovery method yields a better reconstruction result than existing methods. By implementing the joint sparse recovery method, the accuracy and efficiency of DOA estimation are improved in both passive and active sensing cases. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of distributed detection in tree topologies in the presence of Byzantines. The expression for minimum attacking power required by the Byzantines to blind the fusion center (FC) is obtained. More specifically, we show that when more than a certain fraction of individual node decisions are falsified, the decision fusion scheme becomes completely incapable. We obtain closed-form expressions for the optimal attacking strategies that minimize the detection error exponent at the FC. We also look at the possible countermeasures from the FC's perspective to protect the network from these Byzantines. We formulate the robust topology design problem as a bi-level program and provide an efficient algorithm to solve it. We also provide some numerical results to gain insights into the solution. [ABSTRACT FROM PUBLISHER]

In this paper, a recursive sliding transform (RST) algorithm is proposed for the fast implementation of the Walsh Hadamard Transform (WHT) on sliding windows. The proposed RST algorithm accelerates the sliding WHT process by recursively reducing the order of WHT. Theoretical analysis shows that the proposed RST algorithm requires only 1.33 additions per sample for each WHT basis vector regardless of the size or dimension of the basis vector. The computational requirement of the proposed RST algorithm is the lowest among existing fast sliding WHT algorithms. [ABSTRACT FROM PUBLISHER]

We study distributed composite optimization over networks: agents minimize a sum of smooth (strongly) convex functions–the agents’ sum-utility–plus a nonsmooth (extended-valued) convex one. We propose a general unified algorithmic framework for such a class of problems and provide a convergence analysis leveraging the theory of operator splitting. Distinguishing features of our scheme are: (i) When each of the agent’s functions is strongly convex, the algorithm converges at a linear rate, whose dependence on the agents’ functions and network topology is decoupled; (ii) When the objective function is convex (but not strongly convex), similar decoupling as in (i) is established for the coefficient of the proved sublinear rate. This also reveals the role of function heterogeneity on the convergence rate. (iii) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity; and (iv) A by-product of our analysis is a tuning recommendation for several existing (non-accelerated) distributed algorithms yielding provably faster (worst-case) convergence rate for the class of problems under consideration. [ABSTRACT FROM AUTHOR]

We consider the sparse phase retrieval problem of recovering a sparse signal $\mathbf {x}$ in $\mathbb {R}^d$ from intensity-only measurements in dimension $d \geq 2$. Sparse phase retrieval can often be equivalently formulated as the problem of recovering a signal from its autocorrelation, which is in turn directly related to the combinatorial problem of recovering a set from its pairwise differences. In one spatial dimension, this problem is well studied and known as the turnpike problem. In this work, we present MISTR (Multidimensional Intersection Sparse supporT Recovery), an algorithm which exploits this formulation to recover the support of a multidimensional signal from magnitude-only measurements. MISTR takes advantage of the structure of multiple dimensions to provably achieve the same accuracy as the best one-dimensional algorithms in dramatically less time. We prove theoretically that MISTR correctly recovers the support of signals distributed as a Gaussian point process with high probability as long as sparsity is at most $\mathcal {O}(n^{d\theta })$ for any $\theta < 1/2$ , where $n^d$ represents pixel size in a fixed image window. In the case that magnitude measurements are corrupted by noise, we provide a thresholding scheme with theoretical guarantees for sparsity at most $\mathcal {O}(n^{d\theta })$ for $\theta < 1/4$ that obviates the need for MISTR to explicitly handle noisy autocorrelation data. Detailed and reproducible numerical experiments demonstrate the effectiveness of our algorithm, showing that in practice MISTR enjoys time complexity which is nearly linear in the size of the input. [ABSTRACT FROM AUTHOR]

We consider stochastic optimization of a smooth non-convex loss function with a convex non-smooth regularizer. In the online setting, where a single sample of the stochastic gradient of the loss is available at every iteration, the problem can be solved using the proximal stochastic gradient descent (SGD) algorithm and its variants. However in many problems, especially those arising in communications and signal processing, information beyond the stochastic gradient may be available thanks to the structure of the loss function. By constructing a strongly convex surrogate of the loss function at every iteration, the stochastic SCA algorithms can exploit the structural properties of the loss function. In this work, we take a closer look at the stochastic SCA algorithm and develop its asynchronous variant which can be used for resource allocation in wireless networks. While the stochastic SCA algorithm is known to converge asymptotically, its iteration complexity has not been well-studied, and is the focus of the current work. The insights obtained from the non-asymptotic analysis allow us to develop a more practical asynchronous variant of the stochastic SCA algorithm which allows the use of surrogate calculated in earlier iterations. We characterize precise bound on the maximum delay the algorithm can tolerate, while still achieving the same convergence rate. We apply the algorithm to the problem of linear precoding in wireless sensor networks, where it can be implemented at low complexity but is shown to perform well in practice. [ABSTRACT FROM AUTHOR]

We study a new stochastic multi-player multi-armed bandits (MP-MAB) problem, where the reward distribution changes if a collision occurs on the arm. Existing literature always assumes a zero reward for involved players if collision happens, but for applications such as cognitive radio, the more realistic scenario is that collision reduces the mean reward but not necessarily to zero. We focus on the more practical no-sensing setting where players do not perceive collisions directly, and propose the Error-Correction Collision Communication (EC3) algorithm that models implicit communication as a reliable communication over noisy channel problem, for which random coding error exponent is used to establish the optimal regret that no communication protocol can beat. Finally, optimizing the tradeoff between code length and decoding error rate leads to a regret that approaches the centralized MP-MAB regret, which represents a natural lower bound. Experiments with practical error-correction codes on both synthetic and real-world datasets demonstrate the superiority of EC3. In particular, the results show that the choice of coding schemes has a profound impact on the regret performance. [ABSTRACT FROM AUTHOR]

Learning the joint probability of random variables (RVs) is the cornerstone of statistical signal processing and machine learning. However, direct nonparametric estimation for high-dimensional joint probability is in general impossible, due to the curse of dimensionality. Recent work has proposed to recover the joint probability mass function (PMF) of an arbitrary number of RVs from three-dimensional marginals, leveraging the algebraic properties of low-rank tensor decomposition and the (unknown) dependence among the RVs. Nonetheless, accurately estimating three-dimensional marginals can still be costly in terms of sample complexity, affecting the performance of this line of work in practice in the sample-starved regime. Using three-dimensional marginals also involves challenging tensor decomposition problems whose tractability is unclear. This work puts forth a new framework for learning the joint PMF using only pairwise marginals, which naturally enjoys a lower sample complexity relative to the third-order ones. A coupled nonnegative matrix factorization (CNMF) framework is developed, and its joint PMF recovery guarantees under various conditions are analyzed. Our method also features a Gram–Schmidt (GS)-like algorithm that exhibits competitive runtime performance. The algorithm is shown to provably recover the joint PMF up to bounded error in finite iterations, under reasonable conditions. It is also shown that a recently proposed economical expectation maximization (EM) algorithm guarantees to improve upon the GS-like algorithm's output, thereby further lifting up the accuracy and efficiency. Real-data experiments are employed to showcase the effectiveness. [ABSTRACT FROM AUTHOR]

We propose an interpretable graph neural network framework to denoise single or multiple noisy graph signals. The proposed graph unrolling networks expand algorithm unrolling to the graph domain and provide an interpretation of the architecture design from a signal processing perspective. We unroll an iterative denoising algorithm by mapping each iteration into a single network layer where the feed-forward process is equivalent to iteratively denoising graph signals. We train the graph unrolling networks through unsupervised learning, where the input noisy graph signals are used to supervise the networks. By leveraging the learning ability of neural networks, we adaptively capture appropriate priors from input noisy graph signals. A core component of graph unrolling networks is the edge-weight-sharing graph convolution operation, which parameterizes each edge weight by a trainable kernel function whose trainable parameters are shared by all the edges. The proposed convolution is permutation-equivariant and can flexibly adjust the edge weights to various graph signals. We further consider two special cases of this class of networks, graph unrolling sparse coding (GUSC) and graph unrolling trend filtering (GUTF), by unrolling sparse coding and trend filtering, respectively. To validate the proposed methods, we conduct extensive experiments on both real-world datasets and simulated datasets, and demonstrate that our methods have smaller denoising errors than conventional denoising algorithms and state-of-the-art graph neural networks. For denoising a single smooth graph signal, the normalized mean square error of the proposed networks is around 40% and 60% lower than that of graph Laplacian denoising and graph wavelets, respectively. [ABSTRACT FROM AUTHOR]

In this work, a gradient-based primal-dual method of multipliers is proposed for solving a class of linearly constrained non-convex problems. We show that with random initialization of the primal and dual variables, the algorithm is able to compute second-order stationary points (SOSPs) with probability one. Further, we present applications of the proposed method in popular signal processing and machine learning problems such as decentralized matrix factorization and decentralized training of overparameterized neural networks. One of the key steps in the analysis is to construct a new loss function for these problems such that the required convergence conditions (especially the gradient Lipschitz conditions) can be satisfied without changing the global optimal points. [ABSTRACT FROM AUTHOR]

This work focuses on the problem of unraveling nonlinearly mixed latent components in an unsupervised manner. The latent components are assumed to reside in the probability simplex, and are transformed by an unknown post-nonlinear mixing system. This problem finds various applications in signal and data analytics, e.g., nonlinear hyperspectral unmixing, image embedding, and nonlinear clustering. Linear mixture learning problems are already ill-posed, as identifiability of the target latent components is hard to establish in general. With unknown nonlinearity involved, the problem is even more challenging. Prior work offered a function equation-based formulation for provable latent component identification. However, the identifiability conditions are somewhat stringent and unrealistic. In addition, the identifiability analysis is based on the infinite sample (i.e., population) case, while the understanding for practical finite sample cases has been elusive. Moreover, the algorithm in the prior work trades model expressiveness with computational convenience, which often hinders the learning performance. Our contribution is threefold. First, new identifiability conditions are derived under largely relaxed assumptions. Second, comprehensive sample complexity results are presented—which are the first of the kind. Third, a constrained autoencoder-based algorithmic framework is proposed for implementation, which effectively circumvents the challenges in the existing algorithm. Synthetic and real experiments corroborate our theoretical analyses. [ABSTRACT FROM AUTHOR]

Carrier frequency offset (CFO) and channel estimation is a classic topic with a large body of prior work using the maximum likelihood (ML) approach together with the Cramér-Rao lower bound (CRLB) analysis. We give the maximum a posteriori probability (MAP) estimation solution, which is particularly useful for tracking. Unlike the ML cases, the corresponding Bayesian CRLB (BCRLB) shows a clear relation with parameters and low complexity algorithms are provided to achieve the BCRLB in almost all SNR range. Among them, the universal algorithm takes a new approach and avoids error floors of the traditional approach. We assume that the time invariant MIMO channel within a packet can have spatial correlation and nonzero mean. The estimation is based on pilot signals. An unexpected result is that the joint MAP estimation is equivalent to an individual MAP estimation of the frequency offset first, again different from the ML results. We provide insight on the pilot/training signal design based on the BCRLB. Unlike past algorithms that trade performance and/or complexity for the accommodation of time varying channels, the MAP solution provides a different route for dealing with time variation. Within a short enough (segment of) packet where the channel and CFO are approximately time invariant, the low complexity algorithm can be employed. Similar to the belief propagation, the estimation of the previous (segment of) packet can serve as the prior knowledge for the next (segment of) packet. [ABSTRACT FROM AUTHOR]

This article proposes a new class of Real Elliptically Skewed (RESK) distributions and associated clustering algorithms that integrate robustness and skewness into a single unified cluster analysis framework. Non-symmetrically distributed and heavy-tailed data clusters have been reported in a variety of real-world applications. Robustness is essential because a few outlying observations can severely obscure the cluster structure. The RESK distributions are a generalization of the Real Elliptically Symmetric (RES) distributions. To estimate the cluster parameters and memberships, we derive an expectation maximization (EM) algorithm for arbitrary RESK distributions. Special attention is given to a new robust skew-Huber M-estimator, which is also the approximate maximum likelihood estimator (MLE) for the skew-Huber distribution, that belongs to the RESK class. Numerical experiments on simulated and real-world data confirm the usefulness of the proposed methods for skewed and heavy-tailed data sets. [ABSTRACT FROM AUTHOR]

We focus on over-the-air (OTA) Federated Learning (FL), which has been suggested recently to reduce the communication overhead of FL due to the repeated transmissions of the model updates by a large number of users over the wireless channel. In OTA FL, all users simultaneously transmit their updates as analog signals over a multiple access channel, and the server receives a superposition of the analog transmitted signals. However, this approach results in the channel noise directly affecting the optimization procedure, which may degrade the accuracy of the trained model. We develop a Convergent OTA FL (COTAF) algorithm which enhances the common local stochastic gradient descent (SGD) FL algorithm, introducing precoding at the users and scaling at the server, which gradually mitigates the effect of noise. We analyze the convergence of COTAF to the loss minimizing model and quantify the effect of a statistically heterogeneous setup, i.e. when the training data of each user obeys a different distribution. Our analysis reveals the ability of COTAF to achieve a convergence rate similar to that achievable over error-free channels. Our simulations demonstrate the improved convergence of COTAF over vanilla OTA local SGD for training using non-synthetic datasets. Furthermore, we numerically show that the precoding induced by COTAF notably improves the convergence rate and the accuracy of models trained via OTA FL. [ABSTRACT FROM AUTHOR]

In this paper, we consider performance analysis of the decentralized power method for the eigendecomposition of the sample covariance matrix based on the averaging consensus protocol. An analytical expression of the second order statistics of the eigenvectors obtained from the decentralized power method, which is required for computing the mean square error (MSE) of subspace-based estimators, is presented. We show that the decentralized power method is not an asymptotically consistent estimator of the eigenvectors of the true measurement covariance matrix unless the averaging consensus protocol is carried out over an infinitely large number of iterations. Moreover, we introduce the decentralized ESPRIT algorithm which yields fully decentralized direction-of-arrival (DOA) estimates. Based on the performance analysis of the decentralized power method, we derive an analytical expression of the MSE of DOA estimators using the decentralized ESPRIT algorithm. The validity of our asymptotic results is demonstrated by simulations. [ABSTRACT FROM PUBLISHER]

The construction of highly incoherent frames, sequences of vectors placed on the unit hyper sphere of a finite dimensional Hilbert space with low correlation between them, has proven very difficult. Algorithms proposed in the past have focused on minimizing the absolute value off-diagonal entries of the Gram matrix of these structures. Recently, a method based on convex optimization that operates directly on the vectors of the frame has been shown to produce promising results. This paper gives a detailed analysis of the optimization problem at the heart of this approach and, based on these insights, proposes a new method that substantially outperforms the initial approach and all current methods in the literature for all types of frames, with low and high redundancy. We give extensive experimental results that show the effectiveness of the proposed method and its application to optimized compressed sensing. [ABSTRACT FROM PUBLISHER]

Linear phase is an important characteristic of digital filters in many signal processing applications. In this paper, two iterative reweighted minimax phase error algorithms are proposed to design nearly linear-phase infinite impulse response (IIR) digital filters with prescribed or simultaneously minimized magnitude errors and preset transition-band gain. In each iteration of the algorithms, a weighted minimax phase error problem with a fixed weight function is firstly solved using a modified Gauss-Newton method with a variable step length, and the weight function of the phase error is then updated using the square root of a modified envelope of the group-delay error of the filter. With the proposed methods, both very small phase error and group-delay error have been obtained while meeting the requirements on the passband and stopband magnitude errors and the transition-band gain. Design examples demonstrate the effectiveness of the proposed methods and the excellent performance of the designed filters. [ABSTRACT FROM PUBLISHER]

In this paper, an optimal unbiased finite impulse response (OUFIR) filter is proposed as a linking solution between the unbiased FIR (UFIR) filter and the Kalman filter (KF). We first derive the batch OUFIR estimator to minimize the mean square error (MSE) subject to the unbiasedness constraint and then find its fast iterative form. It is shown that the OUFIR filter is full horizon (FH) and that its estimate converges to the KF estimate by increasing the horizon length N. As a special feature, we note that the FH OUFIR filter operates almost as fast as the KF. Several other critical properties of the OUFIR filter are illustrated based on simulations and practical applications. Similar to the UFIR filter, and contrary to the KF, the OUFIR filter is highly insensitive to the initial conditions. It has much better robustness than KF against temporary model uncertainties. Finally, the OUFIR filter allows for ignoring system noise, which is typically not well known to the engineer. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of multiple human target tracking in a sequence of video data. A solution is proposed which is able to deal with the challenges of a varying number of targets, interactions, and when every target gives rise to multiple measurements. The developed novel algorithm comprises variational Bayesian clustering combined with a social force model, integrated within a particle filter with an enhanced prediction step. It performs measurement-to-target association by automatically detecting the measurement relevance. The performance of the developed algorithm is evaluated over several sequences from publicly available data sets: AV16.3, CAVIAR, and PETS2006, which demonstrates that the proposed algorithm successfully initializes and tracks a variable number of targets in the presence of complex occlusions. A comparison with state-of-the-art techniques due to Khan , Laet , and Czyz shows improved tracking performance. [ABSTRACT FROM PUBLISHER]

A multiband-structured subband adaptive filter (MSAF) algorithm was introduced to achieve a fast convergence rate for the correlated input signal. The convergence analysis of the adaptive filter algorithm is an important concept because it provides a guideline to design the adaptive filter. However, the convergence analysis of the MSAF algorithm has not been researched as extensively as that of the normalized least-mean-square algorithm. Therefore, it needs to be researched. In this paper, we present a new approach to the mean-square deviation (MSD) analysis of the MSAF algorithm by using the persistently exciting input and the practical assumption that the stopband attenuation of the prototype filter is high. Unlike the previous analysis, the proposed analysis is possible to be applied to the long-length adaptive filter such as the acoustic echo cancellation. The proposed analysis is also applied to a non-stationary model with a random walk of the optimal weight vector. The simulation results match with the theoretical results in both the transient-state and steady-state MSD. [ABSTRACT FROM AUTHOR]

Greedy pursuit, which includes matching pursuit (MP) and orthogonal matching pursuit (OMP), is an efficient approach for sparse approximation. However, conventional greedy pursuit algorithms designed for inner product space are not robust against outliers. In this paper, we devise a new definition of correlation in \ell p-space with p>0, called \ell p-correlation, and introduce the concept of orthogonality in \ell p-space. Based on the \ell p-correlation and \ell p-orthogonality, which are generalizations of the absolute inner product and orthogonality of inner product space, respectively, we develop three greedy pursuit algorithms, namely, \ell p-MP, \ell p-OMP, and weak \ell p-MP, for robust sparse approximation in the presence of outliers. The convergence of the three algorithms is proved. In particular, the \ell p-norm of the residual of each algorithm decays exponentially. It is revealed that the exponential decay factor in the worst case is related to the minimal \ell p-correlation of the residual and the dictionary. Numerical examples on sparse signal recovery and harmonic retrieval in impulsive noise demonstrate that the \ell p-greedy pursuit algorithms with 0< p< 2 are more outlier-resistant than their counterparts in inner product space. [ABSTRACT FROM PUBLISHER]

Waveform design is a pivotal component of the fully adaptive radar construct. In this paper, we consider waveform design for radar space time adaptive processing (STAP), accounting for the waveform dependence of the clutter correlation matrix. Due to this dependence, in general, the joint problem of receiver filter optimization and radar waveform design becomes an intractable, nonconvex optimization problem, Nevertheless, it is, however, shown to be individually convex either in the filter or in the waveform variables. We derive constrained versions of a) the alternating minimization algorithm, b) proximal alternating minimization, and c) the constant modulus alternating minimization, which, at each step, iteratively optimizes either the STAP filter or the waveform independently. A fast and slow time model permits waveform design in radar STAP, but the primary bottleneck is the computational complexity of the algorithms. [ABSTRACT FROM PUBLISHER]

This paper proposes a framework for the artificial noise assisted secure transmission in multiple-input, multiple-output, multiple antenna eavesdropper (MIMOME) wiretap channels in frequency-division duplexed (FDD) systems. We focus on a practical scenario that only the eavesdroppers’ channel distribution information (CDI) is available and the imperfect channel state information (CSI) of the legitimate receiver is acquired through training and analog feedback. By taking explicitly into account the signaling overhead and training power overhead incurred by channel estimation and feedback, we define the achievable effective ergodic secrecy rate (ESR), and investigate a joint power allocation and training overhead optimization problem for the maximization of effective ESR. We first derive a deterministic approximation for the achievable effective ESR which facilitates the joint optimization. Then, efficient iterative algorithms are proposed to solve the considered nonconvex optimization problem. In particular, in the high-SNR regime, a block coordinate descent method (BCDM) is proposed to handle the joint optimization. In the low-SNR regime, we transform the problem into a sequence of geometric programmings (GPs) and locate its Karush–Kuhn–Tucker (KKT) solution using the successive convex approximation (SCA) method. For the general case of SNR, we maximize the lower bound of the achievable effective ESR. Simulation results corroborate the theoretical analysis and illustrate the secrecy performance of the proposed secure transmission scheme. [ABSTRACT FROM AUTHOR]