Search

This paper deals with joint source-relay-destination beamforming (BF) design for an amplify-and-forward (AF) relay network. Considering the channel state information (CSI) from the relay to the destination is imperfect, we first aim to maximize the worst case received SNR under per-antenna power constraints. The associated optimization problem is then solved in two steps. In the first step, by revealing the rank-one property of the optimal relay BF matrix, we establish the semi-closed form solution of the joint optimal BF design that only depends on a vector variable. Based on this result, in the second step, we propose a low-complexity iterative algorithm to obtain the remaining unknown variable. We also study the problem for minimizing the maximum per-antenna power at the relay while ensuring a received signal-to-noise ratio (SNR) target, and show that it reduces to the SNR maximization problem. Thus the same methods can be applied to solve it. The differences between our result and the existing related work are also discussed in details. In particular, we show that in the perfect CSI case, our algorithm has the same performance but with much lower cost of computational complexity than the existing method. Finally, in the simulation part, we investigate the impact of imperfect CSI on the system performance to verify our analysis. [ABSTRACT FROM PUBLISHER]

In this paper, an efficient compartmental model for real-time node tracking over cognitive wireless sensor networks is proposed. The compartmental model is developed in a multi-sensor fusion framework with cognitive bandwidth utilization. The multi-sensor data attenuation model using radio, acoustic, and visible light signal is first derived using a sum of exponentials model. A compartmental model that selectively combines the multi-sensor data is then developed. The selection of individual sensor data is based on the criterion of bandwidth utilization. The parameters of the compartmental model are computed using the modified Prony estimator, which results in high tracking accuracies. Additional advantages of the proposed method include lower computational complexity and asymptotic distribution of the estimator. Cramer-Rao bound and elliptical error probability analysis are also discussed to highlight the advantages of the compartmental model. Experimental results for real-time node tracking in indoor environment indicate a significant improvement in tracking performance when compared to state-of-the-art methods in literature. [ABSTRACT FROM PUBLISHER]

In this paper, we develop verifiable sufficient conditions and computable performance bounds of \ell1-minimization based sparse recovery algorithms in both the noise-free and noisy cases. We define a family of quality measures for arbitrary sensing matrices as a set of optimization problems, and design polynomial-time algorithms with theoretical global convergence guarantees to compute these quality measures. The proposed algorithms solve a series of second-order cone programs, or linear programs. We derive performance bounds on the recovery errors in terms of these quality measures. We also analytically demonstrate that the developed quality measures are non-degenerate for a large class of random sensing matrices, as long as the number of measurements is relatively large. Numerical experiments show that, compared with the restricted isometry based performance bounds, our error bounds apply to a wider range of problems and are tighter, when the sparsity levels of the signals are relatively low. [ABSTRACT FROM PUBLISHER]

We develop a sampling scheme on the sphere that permits accurate computation of the spherical harmonic transform and its inverse for signals band-limited at L using only L^2 samples. We obtain the optimal number of samples given by the degrees of freedom of the signal in harmonic space. The number of samples required in our scheme is a factor of two or four fewer than existing techniques, which require either 2L^2 or 4L^2 samples. We note, however, that we do not recover a sampling theorem on the sphere, where spherical harmonic transforms are theoretically exact. Nevertheless, we achieve high accuracy even for very large band-limits. For our optimal-dimensionality sampling scheme, we develop a fast and accurate algorithm to compute the spherical harmonic transform (and inverse), with computational complexity comparable with existing schemes in practice. We conduct numerical experiments to study in detail the stability, accuracy and computational complexity of the proposed transforms. We also highlight the advantages of the proposed sampling scheme and associated transforms in the context of potential applications. [ABSTRACT FROM PUBLISHER]

Toeplitz-structured linear systems arise often in practical engineering problems. Correspondingly, a number of algorithms have been developed that exploit Toeplitz structure to gain computational efficiency when solving these systems. Early “fast” algorithms required \cal O(n^2) operations, but recent “superfast” algorithms are more efficient. In this work, we present a superfast algorithm for Tikhonov regularization of Toeplitz systems. Using an “extension-and-transformation” technique, our algorithm translates a Tikhonov-regularized Toeplitz system into a type of specialized polynomial problem known as tangential interpolation. Under this formulation, we can compute the solution in only \cal O(KN\log ^2 N) operations, where K is the number of regularizers and N is on the order of the number of parameters defining the system matrix. Our algorithm is further improved with displacement structure, which reduces the complexity when solving the system for multiple input vectors. We use numerical simulations to demonstrate our algorithm's complexity and accuracy. [ABSTRACT FROM PUBLISHER]

We present a novel method for the design of finite impulse response (FIR) filters with discrete coefficients that belong in the sum of powers-of-two (POT) space. The importance of this class of filters cannot be overstated, given the ever-increasing number of applications for which a specific hardware implementation is needed. Filters that have coefficients that belong to such a class are also referred to as multiplierless filters, given that the operations performed by the filter can all be implemented by using appropriately designed shifts of the input data, making them a perfect choice whenever implementation simplicity and processing speed are the ultimate goal. To produce such a design, we employ a vector successive approximation technique successfully used in data compression that has a very low computational complexity, the Matching Pursuits Generalized BitPlanes algorithm (MPGBP). We derive optimality conditions for the approximation dictionary. We compare filters obtained with the proposed method with those derived in previous works. Based on this comparative analysis, we show that this new and powerful way of producing the filters' coefficients is also among the simplest available in the literature. [ABSTRACT FROM PUBLISHER]

The fundamental problem of interest here is soft-input–soft-output multiple-input–multiple-output (MIMO) detection. We propose a method, referred to as subspace marginalization with interference suppression (SUMIS), that yields unprecedented performance at low and fixed (deterministic) complexity. Our method provides a well-defined tradeoff between computational complexity and performance. Apart from an initial sorting step consisting of selecting channel-matrix columns, the algorithm involves no searching nor algorithmic branching; hence the algorithm has a completely predictable run-time and allows for a highly parallel implementation. We numerically assess the performance of SUMIS in different practical settings: full/partial channel state information, sequential/iterative decoding, and low/high rate outer codes. We also comment on how the SUMIS method performs in systems with a large number of transmit antennas. [ABSTRACT FROM PUBLISHER]

Integer least-squares problems, concerned with solving a system of equations where the components of the unknown vector are integer-valued, arise in a wide range of applications. In many scenarios the unknown vector is sparse, i.e., a large fraction of its entries are zero. Examples include applications in wireless communications, digital fingerprinting, and array-comparative genomic hybridization systems. Sphere decoding, commonly used for solving integer least-squares problems, can utilize the knowledge about sparsity of the unknown vector to perform computationally efficient search for the solution. In this paper, we formulate and analyze the sparsity-aware sphere decoding algorithm that imposes \ell_0-norm constraint on the admissible solution. Analytical expressions for the expected complexity of the algorithm for alphabets typical of sparse channel estimation and source allocation applications are derived and validated through extensive simulations. The results demonstrate superior performance and speed of sparsity-aware sphere decoder compared to the conventional sparsity-unaware sphere decoding algorithm. Moreover, variance of the complexity of the sparsity-aware sphere decoding algorithm for binary alphabets is derived. The search space of the proposed algorithm can be further reduced by imposing lower bounds on the value of the objective function. The algorithm is modified to allow for such a lower bounding technique and simulations illustrating efficacy of the method are presented. Performance of the algorithm is demonstrated in an application to sparse channel estimation, where it is shown that sparsity-aware sphere decoder performs close to theoretical lower limits. [ABSTRACT FROM PUBLISHER]

Efficient optimization techniques are important to manage interference in emerging dense wireless networks. Here, we address interference management through power control as a general utility maximization problem. For the class of utility functions that are concave in the logarithm of the optimization variables, we propose a power control algorithm based on fixed-point iterations. The iterations converge to the globally optimal power vector. One key benefit is that, for a network with N transmitters and a centralized implementation of the power control algorithm, the computational complexity per iteration of the algorithm is \cal O(N^2). When implemented in a distributed fashion and allowing for a signaling complexity of N messages per iteration, the computation complexity is reduced to \cal O(N). We show that the proposed centralized and distributed versions of the algorithm converge to the optimal power vector at a linear rate. Our numerical results suggest that in most instances, the algorithm takes fewer than ten iterations to converge, even fewer if the initialization is close to the optimal power vector. The proposed algorithm is, therefore, very efficient for power control in slowly fading channels. Furthermore, unlike previous works in the literature, the proposed algorithm does not require the objective function to be separable into a sum of individual utilities. As an example, we present results for power control in a two-hop decode-and-forward cooperative relay network and illustrate the performance gains due to interference management. [ABSTRACT FROM AUTHOR]

In this work the dynamic compressive sensing (CS) problem of recovering sparse, correlated, time-varying signals from sub-Nyquist, non-adaptive, linear measurements is explored from a Bayesian perspective. While there has been a handful of previously proposed Bayesian dynamic CS algorithms in the literature, the ability to perform inference on high-dimensional problems in a computationally efficient manner remains elusive. In response, we propose a probabilistic dynamic CS signal model that captures both amplitude and support correlation structure, and describe an approximate message passing algorithm that performs soft signal estimation and support detection with a computational complexity that is linear in all problem dimensions. The algorithm, DCS-AMP, can perform either causal filtering or non-causal smoothing, and is capable of learning model parameters adaptively from the data through an expectation-maximization learning procedure. We provide numerical evidence that DCS-AMP performs within 3 dB of oracle bounds on synthetic data under a variety of operating conditions. We further describe the result of applying DCS-AMP to two real dynamic CS datasets, as well as a frequency estimation task, to bolster our claim that DCS-AMP is capable of offering state-of-the-art performance and speed on real-world high-dimensional problems. [ABSTRACT FROM AUTHOR]

As a greedy algorithm to recover sparse signals from compressed measurements, orthogonal matching pursuit (OMP) algorithm has received much attention in recent years. In this paper, we introduce an extension of the OMP for pursuing efficiency in reconstructing sparse signals. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple N indices are identified per iteration. Owing to the selection of multiple “correct” indices, the gOMP algorithm is finished with much smaller number of iterations when compared to the OMP. We show that the gOMP can perfectly reconstruct any K-sparse signals (K>1), provided that the sensing matrix satisfies the RIP with \deltaNK<{{\sqrt{N}}\over{\sqrt{K}+3\sqrt{N}}}. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to \ell1-minimization technique with fast processing speed and competitive computational complexity. [ABSTRACT FROM PUBLISHER]

Sparse signal reconstruction algorithms have attracted research attention due to their wide applications in various fields. In this paper, we present a simple Bayesian approach that utilizes the sparsity constraint and a priori statistical information (Gaussian or otherwise) to obtain near optimal estimates. In addition, we make use of the rich structure of the sensing matrix encountered in many signal processing applications to develop a fast sparse recovery algorithm. The computational complexity of the proposed algorithm is very low compared with the widely used convex relaxation methods as well as greedy matching pursuit techniques, especially at high sparsity. [ABSTRACT FROM PUBLISHER]

A linearly-constrained recursive least-squares adaptive filtering algorithm based on the method of weighting and the dichotomous coordinate descent (DCD) iterations is proposed. The method of weighting is employed to incorporate the linear constraints into the least-squares problem. The normal equations of the resultant unconstrained least-squares problem are then solved using the DCD iterations. The proposed algorithm has a significantly smaller computational complexity than the previously proposed constrained recursive least square (CRLS) algorithm while delivering convergence performance on par with CRLS. The effectiveness of the proposed algorithm is demonstrated by simulation examples. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate the challenging problem of joint source and relay optimization for two-way linear non-regenerative multiple-input multiple-output (MIMO) relay communication systems. We derive the optimal structure of the source and relay precoding matrices when linear minimal mean-squared error (MMSE) receivers are used at both destinations in the relay system. We show that for a broad class of frequently used objective functions for MIMO communications such as the MMSE, the maximal mutual information (MMI), and the minimax MSE, the optimal relay and source matrices have a general beamforming structure. This result includes existing works as special cases. Based on this optimal structure, a new iterative algorithm is developed to jointly optimize the relay and source matrices. We also propose a novel suboptimal relay precoding matrix design which significantly reduces the computational complexity of the optimal design with only a marginal performance degradation. Interestingly, we show that this suboptimal relay matrix is indeed optimal for some special cases. The performance of the proposed algorithms are demonstrated by numerical simulations. It is shown that the novel minimax MSE-based two-way relay system has a better bit-error-rate (BER) performance compared with existing two-way relay systems using the MMSE and the MMI criteria. [ABSTRACT FROM PUBLISHER]

This work proposes a new tensor-based approach to solve the problem of blind identification of underdetermined mixtures of complex-valued sources exploiting the cumulant generating function (CGF) of the observations. We show that a collection of second-order derivatives of the CGF of the observations can be stored in a third-order tensor following a constrained factor (CONFAC) decomposition with known constrained structure. In order to increase the diversity, we combine three derivative types into an extended third-order CONFAC decomposition. A detailed uniqueness study of this decomposition is provided, from which easy-to-check sufficient conditions ensuring the essential uniqueness of the mixing matrix are obtained. From an algorithmic viewpoint, we develop a CONFAC-based enhanced line search (CONFAC-ELS) method to be used with an alternating least squares estimation procedure for accelerated convergence, and also analyze the numerical complexities of two CONFAC-based algorithms (namely, CONFAC-ALS and CONFAC-ELS) in comparison with the Levenberg-Marquardt (LM)-based algorithm recently derived to solve the same problem. Simulation results compare the proposed approach with some higher-order methods. Our results also corroborate the advantages of the CONFAC-based approach over the competing LM-based approach in terms of performance and computational complexity. [ABSTRACT FROM PUBLISHER]

Sum-rate maximization in two-way amplify-and-forward (AF) multiple-input multiple-output (MIMO) relaying belongs to the class of difference-of-convex functions (DC) programming problems. DC programming problems occur also in other signal processing applications and are typically solved using different modifications of the branch-and-bound method which, however, does not have any polynomial time complexity guarantees. In this paper, we develop two efficient polynomial time algorithms for the sum-rate maximization in two-way AF MIMO relaying. The first algorithm guarantees to find at least a Karush-Kuhn-Tucker (KKT) solution. There is a strong evidence, however, that such a solution is actually globally optimal. The second algorithm that is based on the generalized eigenvectors shows the same performance as the first one with reduced computational complexity. The objective function of the problem is represented as a product of quadratic fractional ratios and parameterized so that its convex part (versus the concave part) contains only one (or two) optimization variables. One of the algorithms is called POlynomial Time DC (POTDC) and is based on semi-definite programming (SDP) relaxation, linearization, and an iterative Newton-type search over a single parameter. The other algorithm is called RAte-maximization via Generalized EigenvectorS (RAGES) and is based on the generalized eigenvectors method and an iterative search over two (or one, in its approximate version) optimization variables. We derive an upper-bound for the optimal value of the corresponding optimization problem and show by simulations that this upper-bound is achieved by both algorithms. It provides an evidence that the algorithms find a global optimum. The proposed methods are also superior to other state-of-the-art algorithms. [ABSTRACT FROM PUBLISHER]

This paper presents two new iterative multiuser detection algorithms for spectrally efficient frequency division multiple access continuous phase modulation in additive white Gaussian noise. The detectors are derived from the sum-product algorithm and the factor graph framework, performing approximate maximum a posteriori (MAP) bit detection. A factor graph of the actual multiuser detection problem is considered, rather than only factor graphs of the individual single user detection problems combined with ad-hoc inter-user interference cancellation. The practical implementation of the detectors is based on the assumption that a suitable set of sum-product messages can be approximated by a Gaussian distribution. This methodology allows to considerably reduce the computational complexity and memory size requirements as compared to a straightforward application of the sum-product rules. The proposed algorithms further succeed in achieving a good error performance. [ABSTRACT FROM PUBLISHER]

In this paper, parameter estimation for R-dimensional (R -D) sinusoids with R >; 2 in additive white Gaussian noise is addressed. With the use of tensor algebra and principal-singular-vector utilization for modal analysis, the sinusoidal parameters at one dimension are first accurately estimated according to an iterative procedure which utilizes the linear prediction property and weighted least squares. The damping factors and frequencies in the remaining dimensions are then solved such that pairing of the R-D parameters is automatically achieved. Algorithm modification for a single R -D tone is made and it is proved that the frequency estimates are asymptotically unbiased while their variances approach Cramér-Rao lower bound at sufficiently high signal-to-noise ratio conditions. Computer simulations are also included to compare the proposed approach with conventional R -D harmonic retrieval schemes in terms of mean square error performance and computational complexity. [ABSTRACT FROM PUBLISHER]

Classical Higher-Order Statistics (HOS, in the form of high-order cumulants) are a powerful tool in the context of multivariate statistical analysis, often entailing valuable statistical information beyond Second-Order statistics (SOS), albeit at the expense of increased computational and notational complexity and compromised statistical stability (in the sense that longer observation intervals might be required in order to fully realize the advantages of HOS over SOS). In this paper, we consider new generic tools, offering the structural simplicity and controllable statistical stability of SOS on the one hand, yet retaining higher-order statistical information on the other hand. While cumulants are related to high-order derivatives of the log characteristic function at the origin, our new tools are related to lower-order (first and second) derivatives away from the origin, at locations called processing-points, and are termed charmean (or charm, in short) and charrelation. The charm and charrelation coincide with the classical mean and covariance (resp.) when the processing-point approaches the origin, but can offer continuously tunable tradeoffs between statistical stability and information contents as the processing-point is dragged away from the origin. Our goal in this paper is to introduce the underlying mathematical-statistical concepts for the development and analysis of charm- and charrelation-based estimation. We derive explicit expressions for the asymptotic bias and variance of their sample-estimates, which in turn enable data-driven selection of the processing-points, so as to minimize the predicted mean square estimation error in a given problem-as we demonstrate in several simulation examples. [ABSTRACT FROM PUBLISHER]

We propose a low-complexity dual-diagonal (DD-) linear-minimum-mean-square-error (LMMSE) channel estimation algorithm for orthogonal frequency-division multiplexing (OFDM) systems involving iterative channel estimation and signal detection. Computational complexity and mean-square-error (MSE) analysis are presented to evaluate the efficiency of the proposed algorithm. A closed-form expression is derived for the asymptotic MSE of the DD-LMMSE channel estimator. Both analysis and numerical results show that DD-LMMSE performs close to the well-known LMMSE estimator with much lower complexity. [ABSTRACT FROM PUBLISHER]

This paper exemplifies that the use of multiple kernels leads to efficient adaptive filtering for nonlinear systems. Two types of multikernel adaptive filtering algorithms are proposed. One is a simple generalization of the kernel normalized least mean square (KNLMS) algorithm refid="ref2"/ , adopting a coherence criterion for dictionary designing. The other is derived by applying the adaptive proximal forward-backward splitting method to a certain squared distance function plus a weighted block \ell1 norm penalty, encouraging the sparsity of an adaptive filter at the block level for efficiency. The proposed multikernel approach enjoys a higher degree of freedom than those approaches which design a kernel as a convex combination of multiple kernels. Numerical examples show that the proposed approach achieves significant gains particularly for nonstationary data as well as insensitivity to the choice of some design-parameters. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel low-complexity variable forgetting factor (VFF) mechanism for blind adaptive constrained constant modulus (CCM) recursive least squares (RLS) algorithms applied to linear interference suppression in direct-sequence code-division multiple access (DS-CDMA) systems. The proposed variable forgetting factor mechanism employs an updated component related to the time average of the constant modulus (CM) cost function to automatically adjust the forgetting factor in order to ensure good tracking of the interference and the channel. Convergence and tracking analyses are carried out. Analytical expressions for predicting the mean-squared error of the proposed adaptation technique are obtained. Simulation results are presented for nonstationary environments and show that the proposed variable forgetting factor mechanism achieves superior performance to previously reported methods at a reduced complexity. [ABSTRACT FROM PUBLISHER]

This correspondence considers a MIMO relay downlink system using precoding and limited feedback. Since the conventional precoding matrices are directly obtained by treating the quantized channel state information (CSI) feedback as real CSI, we propose an optimized relay precoding strategy by taking both effects of channel quantization error and feedback delay into account. Conditioned on the outdated CSI quantization available at the relay station, the relay precoding is optimized via minimizing an expected mean-square error (MSE) criterion over CSI mismatches. By using Karush-Kuhn-Tucker (KKT) conditions, a closed-form solution to the relay design is achieved with comparable computational complexity relative to the conventional approach. Numerical results verify the effectiveness of the proposed scheme. [ABSTRACT FROM PUBLISHER]

Cooperative localization of mobile sensor networks is a fundamental problem which becomes challenging for anchorless networks where there is no pre-existing infrastructure to rely on. Two cooperative mobile network tracking algorithms based on novel dynamic multidimensional scaling (MDS) ideas are proposed. The algorithms are also extended to operate in partially connected networks. Compared with recently proposed algorithms based on the extended and unscented Kalman filter (EKF and UKF), the proposed algorithms have a considerably lower computational complexity. Furthermore, model-independence, scalability, as well as an acceptable accuracy make our proposed algorithms a good choice for practical mobile network tracking. [ABSTRACT FROM PUBLISHER]

We propose a widely linear multistage Wiener filter (WL-MSWF) receiver to suppress inter-/intra-symbol interference, multiuser interference, and narrowband interference in a high data rate direct-sequence ultra wideband (DS-UWB) system. The proposed WL receiver fully exploits the second-order statistics of the received signal, yielding a smaller Minimum Mean Square Error (MMSE) than the linear receiver. The WL-MSWF receiver mainly consists of a low-rank transformation and an adaptive reduced-rank after. The rank-reduction is achieved via a transformation matrix. Based on the linear MSWF concept, two constructions of this rank-reduction matrix, namely total WL (TWL) and quasi WL (QWL), are proposed. We develop stochastic gradient (SG) and recursive least squares (RLS) adaptive versions of the proposed TWL/QWL-MSWF and theoretically analyze their convergence behavior. The comparison of the proposed TWL/QWL-MSWF and the existing algorithms is carried out in terms of the computational complexity and the resulting MMSE performance. Extensive simulation results show that the proposed TWL/QWL-MSWF schemes outperform the existing schemes in both convergence and steady-state performance under various conditions. [ABSTRACT FROM PUBLISHER]

While loopy belief propagation (LBP) performs reasonably well for inference in some Gaussian graphical models with cycles, its performance is unsatisfactory for many others. In particular for some models LBP does not converge, and in general when it does converge, the computed variances are incorrect (except for cycle-free graphs for which belief propagation (BP) is non-iterative and exact). In this paper we propose feedback message passing (FMP), a message-passing algorithm that makes use of a special set of vertices (called a feedback vertex set or FVS) whose removal results in a cycle-free graph. In FMP, standard BP is employed several times on the cycle-free subgraph excluding the FVS while a special message-passing scheme is used for the nodes in the FVS. The computational complexity of exact inference is O(k2n), where is the number of feedback nodes, and is the total number of nodes. When the size of the FVS is very large, FMP is computationally costly. Hence we propose approximate FMP, where a pseudo-FVS is used instead of an FVS, and where inference in the non-cycle-free graph obtained by removing the pseudo-FVS is carried out approximately using LBP. We show that, when approximate FMP converges, it yields exact means and variances on the pseudo-FVS and exact means throughout the remainder of the graph. We also provide theoretical results on the convergence and accuracy of approximate FMP. In particular, we prove error bounds on variance computation. Based on these theoretical results, we design efficient algorithms to select a pseudo-FVS of bounded size. The choice of the pseudo-FVS allows us to explicitly trade off between efficiency and accuracy. Experimental results show that using a pseudo-FVS of size no larger than log (n), this procedure converges much more often, more quickly, and provides more accurate results than LBP on the entire graph. [ABSTRACT FROM PUBLISHER]

Total least squares (TLS) estimation is a popular solution technique for overdetermined systems of linear equations with a noisy data matrix. In this paper, we revisit the distributed total least squares (D-TLS) algorithm, which operates in an ad hoc network, where each node has access to a subset of the linear equations. The D-TLS algorithm computes the TLS solution of the full system of equations in a fully distributed fashion (without fusion center). To reduce the large computational complexity due to an eigenvalue decomposition (EVD) at every node and in each iteration, we modify the D-TLS algorithm based on inverse power iterations (IPIs). In each step of the modified algorithm, a single IPI is performed, which significantly reduces the computational complexity. We show that this IPI-based D-TLS algorithm still converges to the network-wide TLS solution under certain assumptions, which are often satisfied in practice. We provide simulation results to demonstrate the convergence of the algorithm, even when some of these assumptions are not satisfied. [ABSTRACT FROM PUBLISHER]

Notwithstanding the popularity of conventional clustering algorithms such as K-means and probabilistic clustering, their clustering results are sensitive to the presence of outliers in the data. Even a few outliers can compromise the ability of these algorithms to identify meaningful hidden structures rendering their outcome unreliable. This paper develops robust clustering algorithms that not only aim to cluster the data, but also to identify the outliers. The novel approaches rely on the infrequent presence of outliers in the data, which translates to sparsity in a judiciously chosen domain. Leveraging sparsity in the outlier domain, outlier-aware robust K-means and probabilistic clustering approaches are proposed. Their novelty lies on identifying outliers while effecting sparsity in the outlier domain through carefully chosen regularization. A block coordinate descent approach is developed to obtain iterative algorithms with convergence guarantees and small excess computational complexity with respect to their non-robust counterparts. Kernelized versions of the robust clustering algorithms are also developed to efficiently handle high-dimensional data, identify nonlinearly separable clusters, or even cluster objects that are not represented by vectors. Numerical tests on both synthetic and real datasets validate the performance and applicability of the novel algorithms. [ABSTRACT FROM PUBLISHER]

Given a dictionary that consists of multiple blocks and a signal that lives in the range space of only a few blocks, we study the problem of finding a block-sparse representation of the signal, i.e., a representation that uses the minimum number of blocks. Motivated by signal/image processing and computer vision applications, such as face recognition, we consider the block-sparse recovery problem in the case where the number of atoms in each block is arbitrary, possibly much larger than the dimension of the underlying subspace. To find a block-sparse representation of a signal, we propose two classes of nonconvex optimization programs, which aim to minimize the number of nonzero coefficient blocks and the number of nonzero reconstructed vectors from the blocks, respectively. Since both classes of problems are NP-hard, we propose convex relaxations and derive conditions under which each class of the convex programs is equivalent to the original nonconvex formulation. Our conditions depend on the notions of mutual and cumulative subspace coherence of a dictionary, which are natural generalizations of existing notions of mutual and cumulative coherence. We evaluate the performance of the proposed convex programs through simulations as well as real experiments on face recognition. We show that treating the face recognition problem as a block-sparse recovery problem improves the state-of-the-art results by 10% with only 25% of the training data. [ABSTRACT FROM PUBLISHER]

We introduce a recursive adaptive group lasso algorithm for real-time penalized least squares prediction that produces a time sequence of optimal sparse predictor coefficient vectors. At each time index the proposed algorithm computes an exact update of the optimal ℓ1,∞-penalized recursive least squares (RLS) predictor. Each update minimizes a convex but nondifferentiable function optimization problem. We develop an on-line homotopy method to reduce the computational complexity. Numerical simulations demonstrate that the proposed algorithm outperforms the ℓ1 regularized RLS algorithm for a group sparse system identification problem and has lower implementation complexity than direct group lasso solvers. [ABSTRACT FROM PUBLISHER]

We develop fast recursive equalizers to be used in the one-dimensional (1D) or two-dimensional (2D) linear minimum mean-squared error equalization of a known linear finite-length channel. In particular, these equalization algorithms address the communications scenario in which the channel or the prior information on the transmitted symbols may be time varying. The latter case of time-varying priors is especially pertinent for turbo equalization, on which we focus here. We first consider a 1D sliding-window equalizer based on a Cholesky-factorization update and then generalize this approach to the 2D case. Finally, we develop a 2D equalizer that is based on a recursive matrix-inverse update. We summarize each of these algorithms and describe their computational complexities. [ABSTRACT FROM PUBLISHER]

It is known that the design of optimal transmit beamforming vectors for cognitive radio multicast transmission can be formulated as indefinite quadratic optimization programs. Given the challenges of such nonconvex problems, the conventional approach in literature is to recast them as convex semidefinite programs (SDPs) together with rank-one constraints. Then, these nonconvex and discontinuous constraints are dropped allowing for the realization of a pool of relaxed candidate solutions, from which various randomization techniques are utilized with the hope to recover the optimal solutions. However, it has been shown that such approach fails to deliver satisfactory outcomes in many practical settings, wherein the determined solutions are found to be unacceptably far from the actual optimality. On the contrary, we in this contribution tackle the aforementioned optimal beamforming problems differently by representing them as SDPs with additional reverse convex (but continuous) constraints. Nonsmooth optimization algorithms are then proposed to locate the optimal solutions of such design problems in an efficient manner. Our thorough numerical examples verify that the proposed algorithms offer almost global optimality whilst requiring relatively low computational load. [ABSTRACT FROM AUTHOR]

Estimation of the covariance matrix and its inverse, the precision matrix, in high-dimensional situations is of great interest in many applications. In this paper, we focus on the estimation of a class of sparse precision matrices which are assumed to be approximately inversely closed for the case that the dimensionality p can be much larger than the sample size n, which is fundamentally different from the classical case that p < n. Different in nature from state-of-the-art methods that are based on penalized likelihood maximization or constrained error minimization, based on the truncated Neumann series representation, we propose a computationally efficient precision matrix estimator that has a computational complexity of O(p^3). We prove that the proposed estimator is consistent in probability and in L^2 under the spectral norm. Moreover, its convergence is shown to be rate-optimal in the sense of minimax risk. We further prove that the proposed estimator is model selection consistent by establishing a convergence result under the entry-wise \infty-norm. Simulations demonstrate the encouraging finite sample size performance and computational advantage of the proposed estimator. The proposed estimator is also applied to a real breast cancer data and shown to outperform existing precision matrix estimators. [ABSTRACT FROM AUTHOR]

This paper investigates the linear precoder design that maximizes the average mutual information of multiple-input multiple-output fading channels with statistical channel state information known at the transmitter. It formulates the design from the standpoint of finite-alphabet inputs, which leads to a problem that is very important in practice but extremely difficult in theory: First, the average mutual information lacks closed-form expression and involves prohibitive computational burden. Second, the optimization over the precoder is nonconcave and thus easily gets stuck in local maxima. To address these issues, this study first derives lower and upper bounds for the average mutual information, in which the computational complexity is reduced by several orders of magnitude compared to calculating the average mutual information directly. It proves that maximizing the bounds is asymptotically optimal and shows that, with a constant shift, the lower bound actually offers a very accurate approximation to the average mutual information for various fading channels. This paper further proposes utilizing the lower bound as a low-complexity and accurate alternative for developing a two-step algorithm to find a near global optimal precoder. Numerical examples demonstrate the convergence and efficacy of the proposed algorithm. Compared to its conventional counterparts, the proposed linear precoding method provides significant performance gain over existing precoding algorithms. The gain becomes more substantial when the spatial correlation of MIMO channels increases. [ABSTRACT FROM AUTHOR]

For single-carrier systems with frequency domain equalization, decision feedback equalization (DFE) performs better than linear equalization and has much lower computational complexity than sequence maximum likelihood detection. The main challenge in DFE is the feedback symbol selection rule. In this paper, we give a theoretical insight on multiple symbol selection, based on sparsity and we present a simple algorithm for DFE. The algorithm converges fast and has a low computational cost. We show how the initial solution can be obtained via convex relaxation instead of linear equalization, and illustrate the impact that the choice of the initial solution has on the bit error rate performance of our algorithm. The algorithm is applicable in several existing wireless communication systems (SC-FDMA, MC-CDMA, MIMO-OFDM). Numerical results illustrate significant performance improvement in terms of bit error rate compared to the MMSE solution. [ABSTRACT FROM AUTHOR]

Intercell interference is the major limiting factor in wireless multicell networks. Recently, it has been shown that significant performance gains can be achieved by cooperation among base stations. Different degrees of cooperation are possible. In this paper, cooperation in the form of intercell interference management is considered. The base stations are equipped with multiple antennas, while the mobile terminals only have a single antenna. The base stations jointly coordinate beamforming and scheduling, and thus perform a weaker form of cooperation among base stations than suggested in recently proposed joint transmission techniques. The terminals treat intercell interference as noise. The corresponding resource allocation problem is cast as a utility maximization problem, which includes common performance objectives such as the arithmetic mean, the geometric mean, and the max-min operation of achievable user rates. The resulting utility maximization problem is a nonconvex optimization problem. After a suitable reformulation, the problem can be solved to global optimality using the framework of monotonic optimization. Although, the numerical complexity of the proposed method is exponential, the reformulation step leads to an optimization problem which only scales in the number of mobile terminals instead of the entire set of physical layer parameters. In essence, the proposed framework represents a powerful tool for computing benchmarks for certain scenarios and utility functions under jointly optimal beamforming and scheduling. [ABSTRACT FROM PUBLISHER]

In the present paper, we propose a novel method for estimating one-dimensional damped and undamped harmonics. Our method utilizes the multiple shift-invariance property comprised in the signal model. We develop a new rank-reduction estimator which is formed as the weighted sum of the individual matrix polynomials obtained from individual shift-invariance equations. The uniqueness conditions for the proposed rank-reduction criteria are derived under the assumption that all samples are available. Moreover, a novel technique for the incomplete data case, where some samples are missing, is presented. In this case, the rank-reduction estimator may suffer from ambiguities. To overcome this problem, we propose an extension of the rank-reduction estimator that is based on polynomial intersection and the properties of the Sylvester matrix. The latter algorithm yields unique estimates of the damped harmonics. The proposed high-resolution techniques are search-free and therefore, they enjoy moderate computational complexity. [ABSTRACT FROM PUBLISHER]

Discrete Fourier transforms over finite fields are significant due to their widespread applications in cryptography and error control codes, which in turn are used in all digital communication and storage systems. Cyclotomic fast Fourier transforms (CFFTs) are of great interest due to their low multiplicative complexities. However, all existing CFFTs are for characteristic-2 fields, and the computational complexities of CFFTs have not been analyzed theoretically. This paper addresses both problems for CFFTs, and has three main contributions to this end. First, we propose an efficient bilinear algorithm to compute Toeplitz matrix vector products (TMVPs), which has a lower computational complexity than existing algorithms, and works on all finite fields as well as the real and complex fields. Second, we propose an efficient algorithm for cyclic convolutions over arbitrary finite fields, which is essential in deriving efficient CFFTs over arbitrary finite fields. Finally, we derive bounds on the additive and multiplicative complexities of CFFTs over arbitrary finite fields. Our results confirm that CFFTs have the smallest multiplicative complexities among all known algorithms. Although their high additive complexities render them asymptotically suboptimal, CFFTs remain valuable since they have the smallest overall complexities for DFTs of up to thousands of symbols in most cases. [ABSTRACT FROM PUBLISHER]

We address the application of the linearly constrained minimum variance (LCMV) beamformer in sensor networks. In signal processing applications, it is common to have a redundancy in the number of nodes, fully covering the area of interest. Here we consider suboptimal LCMV beamformers utilizing only a subset of the available sensors for signal enhancement applications. Multiple desired and interfering sources scenarios in multipath environments are considered. We assume that an oracle entity determines the group of sensors participating in the spatial filtering, denoted as the active sensors. The oracle is also responsible for updating the constraints set according to either sensors or sources activity or dynamics. Any update of the active sensors or of the constraints set necessitates recalculation of the beamformer and increases the power consumption. As power consumption is a most valuable resource in sensor networks, it is important to derive efficient update schemes. In this paper, we derive procedures for adding or removing either an active sensor or a constraint from an existing LCMV beamformer. Closed-form, as well as generalized sidelobe canceller (GSC)-form implementations, are derived. These procedures use the previous beamformer to save calculations in the updating process. We analyze the computational burden of the proposed procedures and show that it is much lower than the computational burden of the straightforward calculation of their corresponding beamformers. [ABSTRACT FROM PUBLISHER]

A wireless communication scenario is considered with K single-antenna source-destination pairs communicating through several half-duplex amplify-and-forward MIMO relays where each source is targeting only one destination. The relay beamforming matrices are designed in order to minimize the total power transmitted from the relays subject to quality of service constraints on the received signal to interference-plus-noise ratio at each destination node. Due to the nonconvexity of this problem, several approximations have been used in the literature to find a computationally efficient solution. A novel solution technique is developed in which the problem is decomposed into a group of second-order cone programs (SOCPs) parameterized by K phase angles; each associated with one of the constraints. An iterative algorithm is proposed to search for the phase angles and the relay beamforming matrices sequentially. However, convergence to the global optimal beamforming matrices cannot be guaranteed. Two methods for searching for the optimal values of the phase angles are proposed (from which the optimal beamforming matrices can be obtained) using grid search and bisection and the convergence of these methods to the global optimal solution of the problem is proved. Numerical simulations are presented showing the superior performance of the proposed algorithms compared to earlier suboptimal approximations at the expense of a moderate increase in the computational complexity. [ABSTRACT FROM PUBLISHER]

In this paper, the problem of joint carrier frequency offset (CFO) and channel estimation for OFDM systems over the fast time-varying frequency-selective channel is explored within the framework of the expectation-maximization (EM) algorithm and parametric channel model. Assuming that the path delays are known, a novel iterative pilot-aided algorithm for joint estimation of the multipath Rayleigh channel complex gains (CG) and the carrier frequency offset (CFO) is introduced. Each CG time-variation, within one OFDM symbol, is approximated by a basis expansion model (BEM) representation. An autoregressive (AR) model is built to statistically characterize the variations of the BEM coefficients across the OFDM blocks. In addition to the algorithm, the derivation of the hybrid Cramér-Rao bound (HCRB) for CFO and CGs estimation in our context of very high mobility is provided. We show that the proposed EM has a lower computational complexity than the optimum maximum a posteriori estimator and yet incurs only an insignificant loss in performance. [ABSTRACT FROM PUBLISHER]

This paper presents new linear time-invariant (LTI) block-based transceivers which employ a reduced amount of redundancy to eliminate the interblock interference. The proposals encompass both multicarrier and single-carrier systems with either zero-forcing or minimum mean-square error (MSE) equalizers. The amount of redundancy ranges from the minimum, \lceilL\over 2\rceil, to the most commonly used value, L, assuming a channel-impulse response of order L. The resulting transceivers allow for superfast equalization of the received data blocks, since they only use fast Fourier transforms and single-tap equalizers in their structures. The paper also includes an MSE analysis of the proposed transceivers with respect to the amount of redundancy. Indeed, we demonstrate that larger amounts of transmitted redundant elements lead to lower MSE of symbols at the receiver end. Computer simulations indicate that, by choosing an appropriate amount of redundancy, our proposals can achieve higher throughputs than the standard superfast multicarrier and single-carrier systems, while keeping the same asymptotic computational complexity for the equalization process. [ABSTRACT FROM PUBLISHER]

Lattice reduction-aided decoding (LRAD) features reduced decoding complexity and near-optimum performance in multiinput multioutput communications. In this paper, a quantitative error-rate analysis of LRAD is presented. To this aim, the proximity factors are defined to measure the worst-case losses in decoding distances associated with the decision region relative to infinite lattice decoding (ILD), namely, closest point search in an infinite lattice. Upper bounds on the proximity factors are derived, which are functions of the dimension n of the lattice alone. The study is then extended to the dual-basis reduction. It is found that the bounds for dual basis reduction may be smaller. Reasonably good bounds are derived in many cases. Proximity factors not only imply the same diversity order in fading channels, but also relate the error probabilities of ILD and LRAD. [ABSTRACT FROM AUTHOR]

Solving linear regression problems based on the total least-squares (TLS) criterion has well-documented merits in various applications, where perturbations appear both in the data vector as well as in the regression matrix. However, existing TLS approaches do not account for sparsity possibly present in the unknown vector of regression coefficients. On the other hand, sparsity is the key attribute exploited by modern compressive sampling and variable selection approaches to linear regression, which include noise in the data, but do not account for perturbations in the regression matrix. The present paper fills this gap by formulating and solving (regularized) TLS optimization problems under sparsity constraints. Near-optimum and reduced-complexity suboptimum sparse (S-) TLS algorithms are developed to address the perturbed compressive sampling (and the related dictionary learning) challenge, when there is a mismatch between the true and adopted bases over which the unknown vector is sparse. The novel S-TLS schemes also allow for perturbations in the regression matrix of the least-absolute selection and shrinkage selection operator (Lasso), and endow TLS approaches with ability to cope with sparse, under-determined “errors-in-variables” models. Interesting generalizations can further exploit prior knowledge on the perturbations to obtain novel weighted and structured S-TLS solvers. Analysis and simulations demonstrate the practical impact of S-TLS in calibrating the mismatch effects of contemporary grid-based approaches to cognitive radio sensing, and robust direction-of-arrival estimation using antenna arrays. [ABSTRACT FROM AUTHOR]

The adaptive estimation of a time-varying parameter vector in a linear Gaussian model is considered where we a priori know that the parameter vector belongs to a known arbitrary subset. We consider a family of efficient recursive estimators for this problem: the recursive constrained maximum likelihood (ML) estimator, the recursive affine minimax, and the recursive minimum mean square error (MMSE) estimator. We show that all three estimators can be substantially simplified by using the recursive weighted least squares (RWLS) algorithm in a first step as the RWLS computes the sufficient statistic for this estimation problem. The recursive constrained ML needs to solve an optimization problem in the second step for the case that the RWLS solution does not fulfill the constraint. In case of affine minimax, we have to solve an optimization problem and to perform an affine transform. The MMSE estimator needs to calculate the mean of a truncated Gaussian density in the second step which is done by Monte Carlo integration. A simple rejection scheme is used to take general constraints for the parameter vector into account. An example shows the superior performance of our proposed estimators in comparison to many other estimators. [ABSTRACT FROM PUBLISHER]