Search

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

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

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]

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]

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 correspondence develops a computationally efficient scheme to select a subset of relay antennas to maximize the achievable sum rate (ASR) of amplify-and-forward multiple-input multiple-output two-way relay channels. To reduce the computational complexity of antenna selection (AS), two sequential AS algorithms, joint AS (JAS) and separate AS (SAS), are proposed. JAS jointly selects a pair of receive-transmit antennas at each sequential step. In contrast, SAS separates receive and transmit AS into a two-stage algorithm; the receive antenna set is selected first, followed by selection of the transmit antennas. Simulation results show that the proposed algorithms achieve nearly the same ASR as compared to an exhaustive search, but with significantly reduced computational complexity. [ABSTRACT FROM PUBLISHER]

Multiple-symbol detection has recently caught attention in ultrawideband (UWB) communications because of its high performance without requiring explicit channel estimation. In this context, the generalized likelihood ratio test (GLRT) for multiple-symbol detection problem is developed to jointly detect multiple symbols, which exhibits considerable error performance improvement over transmitted reference transmissions methods. Unfortunately, the GLRT is a Boolean quadratic programming (BQP) problem, which is generally nondeterministic polynomial hard (NP-hard). In this paper, we propose two near-optimal detectors with polynomial complexity. The first detector performs semidefinite relaxation to approximately solve the BQP problem (called SDP-MSD). The second detector is based on a sphere-based relaxation of the BQP problem [we refer to this as modified unconstrained relaxation multiple-symbol detector (MUR-MSD)]. Both detectors achieve near-optimal performance, while the SDP-MSD performs slightly better than the MUR-MSD at the price of higher computational complexity. Furthermore, the MUR-MSD can be treated as a further nontight relaxation of SDP-MSD. Simulations are utilized to validate our findings and to demonstrate performance robustness to multiaccess interference. [ABSTRACT FROM AUTHOR]

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]

This paper introduces Bayes risk (expected loss) as a criterion for linear equalization. Since the probability of error is equal to the Bayes risk (BR) for a particular binary loss function, this work is a natural generalization of previous works on minimum probability of error (PE) equalizers. Adaptive equalization algorithms are developed that minimize the BR. Like the minimum PE equalizers, the BR algorithms have low computational complexity which is comparable to that of the LMS algorithm. The advantage of the BR criterion is that the loss function can be specified in a manner that accelerates adaptive equalizer convergence relative to the minimum PE adaptive algorithm as illustrated in simulation examples. Besides introducing a new criterion, this paper provides another independent contribution to the field of PE minimizing equalization. While most prior works focus on M-ary QAM type modulations with rectangular decision regions, this paper uses upper bounds on the probabilities of certain events to yield tractable mathematics that apply to two-dimensional constellations with arbitrarily shaped decision regions. The resulting adaptive algorithm use the full information available in the phase of the error signal, whereas previous algorithms use a quantized version of this error phase. [ABSTRACT FROM AUTHOR]

Recently, the problem of optimal spectral balancing (OSB) for digital subscriber lines (DSL) with constrained transmit power has been solved using Lagrange's dual optimization technique and a weighted sum rate maximization (WSRM) approach. In many cases, the total power constraint is not binding. Although, this means a huge computational complexity reduction, the algorithm fails to reach certain points on the rate region (RR). In this paper, an in-depth analytical view of the WSRM approach is provided, and it is shown that when the RR is not strictly convex, the WSRM approach fails to reach certain points on the RR. Moreover, using N-dimensional geometry, a novel iterative facet dividing algorithm (IFDA) capable of reaching any point on the RR is proposed. Analytical and simulation results show that our technique is much more reliable and considerably faster than current algorithms. Moreover, it can be used for a wide range of problems which use WSRM approach, including OSB in the general case. [ABSTRACT FROM AUTHOR]

Iteratively reweighted least-squares (IRLS) algorithms have been successfully used in compressive sensing to reconstruct sparse signals from incomplete linear measurements taken in nonsparse domains. The underlying optimization problem corresponds to finding the vector that solves the ℓp, minimization while explaining the measurements, and IRLS allows to easily control the used value of p, with effect on the number of required measurements. In this paper, we propose a weighting strategy in the reconstruction method based on IRLS in order to add prior information on the support of the sparse domain. Our simulation results show that the use of prior knowledge about positions of at least some of the nonzero coefficients in the sparse domain leads to a reduction in the number of linear measurements required for unambiguous reconstruction. This reduction occurs for all values of p, so that a further reduction can be achieved by decreasing p and using prior information. The proposed weighting scheme also reduces the computational complexity with respect to the IRLS with no prior information, both in terms of number of iterations and computation time. [ABSTRACT FROM AUTHOR]

Time warping finds use in many fields of time series analysis, and it has been effectively implemented in many different application areas. Rather than focusing on a particular application area we approach the general problem definition, and employ principal curves, a powerful machine learning tool, to improve the noise robustness of existing time warping methods. The increasing noise level is the most important problem that leads to unnatural alignments. Therefore, we tested our approach in low signal-to-noise ratio (SNR) signals, and obtained satisfactory results. Moreover, for the signals denoised by principal curve projections we propose a differential equation-based time warping method, which has a comparable performance with lower computational complexity than the existing techniques. [ABSTRACT FROM AUTHOR]

In a multisensor target tracking system, observations produced by sensors typically arrive at a central processor out of sequence. There have been some update algorithms for single out-of-sequence measurement (OOSM). In this paper, we consider optimal centralized update algorithms with multiple asynchronous (different lag time) OOSMs. First, we generalize the optimal update algorithm with single one-step-lag OOSM in [Y. Bar-Shalom, "Update With Out-of-Sequence Measurements in Tracking: Exact Solution," IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS, vol. 38, pp. 769-778, July 2002] to optimal centralized update algorithm with multiple one-step-lag OOSMs. Then, based on best linear unbiased estimation, we present an optimal centralized update algorithm with multiple arbitrary-step-lag OOSMs. Finally, two suboptimal centralized update algorithms are proposed to reduce the computational complexity. A numerical example shows that performances of two suboptimal centralized algorithms are close to that of the optimal centralized update algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a very low-complexity design of variable bandedge linear phase finite-impulse-response (FIR) filters with fixed sharp transition width. The idea is to first decompose the input signal into several channels in the frequency domain. The channel(s) involved with the transition band of the variable filter due to the variation of the bandedge is (are) shaped to produce the required transition band, and then summed up with the channels involved with the passband of the variable filter to produce the required frequency response. The proposed variable filter has extremely low complexity when the transition band is sharp, if compared with other techniques such as the Farrow structure. It is possible that the computational complexity of the variable filter is even lower than that of a corresponding fixed filter with the same transition width and ripple specifications implemented in its direct form. [ABSTRACT FROM AUTHOR]

We derive an improved, approximate, maximum likelihood (ML) estimator for the parameters of a single-component chirp signal in the time domain, which has much lower computational complexity than that of the traditional estimators in the frequency domain. We term it the zero-order amplitude weighted phase-based estimator (AWPE). It is a weighted linear combination of the phases of the received signal samples, where the weights are determined by the amplitudes of the received signals. It achieves better performance than the only existing time-domain estimator in the literature that only exploits the phase information. A phase unwrapping (PU) algorithm is needed to recover the phase information correctly from the received signal samples. Several PU algorithms are compared and analyzed. A new, robust PU algorithm based on the first-order phase differences of the consecutive received signal samples is proposed. This new unwrapping algorithm has smaller PU failure probability than that based directly on the phases of the received signal samples. The need for PU can even be removed by using the second-order phase differences of the consecutive received signal samples. Two additional structures for the ML-based AWPE using the phase differences are derived starting from using the zero-order AWPE obtained. The first is based on the first-order phase differences and the second on the second-order phase differences. When the PU algorithm works perfectly, i.e., no phase unwrapping failure occurs, the estimators based on phase differences do not perform as well as the original one based on absolute phase information due to the increased noise variance. This is also applicable when the chirp parameters take on very small values. However, when no knowledge of the ranges of the chirp parameters is available, and the possible PU failures are taken into account, the estimators based on the phase differences could perform better. Performance analysis of the estimators is given based on an improved phase noise model. It is easy to verify that the estimates obtained are unbiased. The Cramér-Rao lower bound (CRLB) on the mean-square error (MSE) is derived. The MSE performance of the estimators approaches the CRLB at high signal-to-noise ratios. The variance performance of the estimators based on phase differences is analyzed, whose validity is demonstrated by simulation results. [ABSTRACT FROM AUTHOR]

The knowledge of the channel at the transmit side of a communication system can be exploited by using precoding techniques, from which the overall transmission quality might benefit significantly. However, in practical wireless systems, the channel state information is prone to errors, which sometimes deteriorates the performance drastically. In this paper, we address the problem of robust transceiver design in a downlink multiuser system, with respect to the erroneous channel knowledge at the transmitter. The base station is equipped with an antenna array, while users have single antennas. The transceiver optimization is performed under a set of predefined users' quality-of-service constraints, defined as maximum mean square errors, or minimum signal-to-interference-plus-noise ratios (SINRs), which must be satisfied for all disturbances that belong to given, bounded uncertainty sets. Efficient numerical solutions are obtained using semidefinite programming methods from convex optimization theory. The proposed algorithms are found to outperform related approaches in the literature in terms of the achieved performance, while maintaining low computational complexity. The studied uncertainty models are applicable in mitigating typical errors that emerge as a result of quantization or channel estimation. [ABSTRACT FROM AUTHOR]

We present a mean-square-error (MSE) duality between the broadcast channel and the multiple access channel for multiantenna users communicating with a single base station. We introduce three levels of the duality which allow for a problem specific customization with different computational complexities and resolutions. The first level preserves the sum-MSE during the conversion from the uplink to the downlink and vice versa, whereas the second level not only keeps the sum-MSE constant but also ensures the preservation of the individual users' MSEs. The third level involves the finest resolution and pre- serves the individual streams' MSEs and the individual streams' signal-to-interference-and-noise, ratio (SINR) simultaneously. In contrast with hitherto existing MSE-dualities, the proposed sort of duality features a lower complexity since no MSE computation detouring is necessary during the conversion to the dual domain and is capable of handling all combinations of active and passive transmitters and receivers. Moreover, we show how two of these three dualities can be exploited to solve the unweighted total sum-MSE minimization problem and the weighted sum-MSE minimization in the broadcast channel in an efficient way by revealing the hidden convexity in the first case and drastically reducing the computational complexity in the latter case. [ABSTRACT FROM AUTHOR]

Abstract-Adaptive filters of significant order, requiring high computational complexity, are necessary in many applications such as acoustic echo cancellation and wideband active noise control. Successful approaches to lessen the computational complexity of such filters are subband methods, and partial updating schemes where only a part of the filter is updated at each instant. To avoid the time delay introduced by the subband-splitting, delayless structures which reconstructs a fullband filter, producing delayless output, from the adaptive subband filters have been proposed. This paper proposes a delayless subband adaptive filter partial updating scheme, where the general idea is to only update the most misadjusted subband filter(s). Analysis in terms of mean square deviation is presented and shows that the fullband filter convergence speed is significantly increased, even for flat spectrum signals, as compared to traditional periodic subband filter update with the same computational complexity. Echo cancellation simulations with an artificial system to verify the analysis, using both flat spectrum signals and speech, is also presented, as well as offline calculations using signals from a real system. [ABSTRACT FROM AUTHOR]

This correspondence attempts to derive the exact implementation of two nonlinear active noise control (ANC) algorithms, viz. FSLMS and VFXLMS. The concept of reutilizing a part of the computations performed for the first sample while computing the next sample, for a block length of two samples, is exploited here to implement the fast and exact versions of the FSLMS and VFXLMS algorithms which are computationally efficient. Detailed computational complexity analysis for both addition and multiplication requirements is presented to show the advantage of the proposed algorithms. Appropriate simulation experiments are carried out to compare the performance equivalence of the proposed fast algorithms with their original versions. [ABSTRACT FROM AUTHOR]

In this paper, we derive a novel implementation of some very computationally demanding matched filter-bank-based spectral estimators, namely the amplitude and phase estimator (APES), the amplitude spectrum Capon (ASC) estimator, and the power spectrum Capon (PSC) estimator. Filter-bank-based spectral estimation methods that adopt data-dependent filter banks can provide spectra characterized by a significantly improved resolution compared to classical approaches. However, the computational complexity of the currently available implementation algorithms, is extremely high. A novel technique is introduced that provides efficient algorithms for the computation of the APES, ASC, and PSC spectra. The proposed method is based on suitable displacement representations of all pertinent data matrices, that are subsequently utilized for the computation of the associated complex valued polynomials. The computational complexity of the proposed algorithms is lower than all relevant existing methods [ABSTRACT FROM AUTHOR]

In this paper, the generation of sequency-ordered complex Hadamard transform (SCHT) based on the complex Rademacher matrices is presented. The exponential form of SCHT is also derived, and the proof for the unitary property of SCHT is given. Using the sparse matrix factorization, the fast and efficient algorithm to compute the SCHT transform is developed, and its computation load is described. Certain properties of the SCHT matrices are derived and analyzed with the discussion of SCHT applications in spectrum analysis and image watermarking. Relations of SCHT with fast Fourier transform (FFT) and unified complex Hadamard transform (UCHT) are discussed. [ABSTRACT FROM AUTHOR]

A new 2 × 2 full-rate full-diversity linear dispersion space-time block code (STBC) is designed by augmenting the generator of the lattice of the Alamouti's orthogonal STBC and optimizing it according to the criterion of the maximal worst code- word difference determinant. The proposed STBC is proved to satisfy the nonvanishing determinant property and, therefore, to achieve the optimal diversity-multiplexing gain (DMG) tradeoff, while offering a reduced computational complexity of maximum- likelihood (ML) decoding as compared to other existing full-rate STBCs. The performance of our new code is shown to be comparable to that of the best full-rate STBCs known so far. [ABSTRACT FROM AUTHOR]

A low-complexity partial transmit sequence (PTS) technique for reducing the peak-to-average power ratio (PAPR) of an orthogonal frequency division multiplexing (OFDM) signal is presented. Signals at the middle stages of an $N$-point radix FFT using decimation in frequency (DIF) or decimation in time (DIT) are considered for PTS subblocking. We show that DIF has a lower multiplicative complexity than DIT for similar PAPR reduction. A higher radix based FFT achieves better PAPR reduction per stage with less multiplicative complexity compared with a lower radix FFT. We further reduce the computational complexity by proposing a new technique, called decomposition PTS (D-PTS) subblocking, where subblocks are assigned through different stages of the transform. This new technique reduces the multiplicative complexity, while providing PAPR reduction similar to other techniques such as original PTS (O-PTS). Moreover, it has lower additive complexity. [ABSTRACT FROM AUTHOR]

Prefilters are generally applied to the discrete multi-wavelet transform (DMWT) for processing scalar signals. To fully utilize the benefit offered by DMWT, it is important to have the pre-filter designed appropriately so as to preserve the important properties of multiwavelets. To this end, we have recently shown that it is possible to have the prefilter designed to be maximally decimated, yet preserve the linear phase and orthogonal properties as well as the approximation power of multiwavelets. However, such design requires the point of symmetry of each channel of the prefilter to match with the scaling functions of the target multiwavelet system. It can be very difficult to find a compatible filter bank structure; and in some cases, such filter structure simply does not exist, e.g., for multiwavelets of multiplicity 2. In this paper, we suggest a new DMWT structure in which the prefilter is combined with the first stage of DMWT. The advantage of the new structure is twofold. First, since the prefiltering stage is embedded into DMWT, the computational complexity can be greatly reduced. Experimental results show that an over 20% saving in arithmetic operations can be achieved comparing with the traditional DMWT realizations. Second, the new structure provides additional design freedom that allows the resulting prefilters to be maximally decimated, orthogonal and symmetric even for multiwavelets of low multiplicity. We evaluated the new DMWT structure in terms of computational complexity, energy compaction ratio as well as the compression performance when applying to a VQ based image coding system. Satisfactory results are obtained in all cases comparing with the traditional approaches. [ABSTRACT FROM AUTHOR]

We consider multi-input multi-output (MIMO) transmit beamforming under the uniform elemental power constraint. This is a nonconvex optimization problem, and it is usually difficult to find the optimal transmit beamformer. First, we show that for the multi-input single-output (MISO) case, the optimal solution has a closed-form expression. Then we propose a cyclic algorithm for the MIMO case which uses the closed-form MISO optimal solution iteratively. The cyclic algorithm has a low computational complexity and is locally convergent under mild conditions. Moreover, we consider finite-rate feedback methods needed for transmit beamforming. We propose a simple scalar quantization method, as well as a novel vector quantization method. For the latter method, the codebook is constructed under the uniform elemental power constraint and the method is referred as VQ-UEP. We analyze VQ-UEP performance for the MISO case. Specifically, we obtain an approximate expression for the average degradation of the receive signal-to-noise ratio (SNR) caused by VQ-UEP. Numerical examples are provided to demonstrate the effectiveness of our proposed transmit beamformer designs and the finite-rate feedback techniques. [ABSTRACT FROM AUTHOR]

This paper presents a new maximum likelihood (ML) symbol detection algorithm for multiple-input multiple-output (MIMO) systems. To achieve the ML performance with low complexity, we search the integer points corresponding to symbol vectors in increasing order of the distance from the unconstrained least-squares solution. For each integer point, we test if it is the ML solution, and continue the integer point search until one of searched points is determined to be the ML solution. We present an efficient iterative search strategy, which is based on the shortest path algorithm for a graph. The simulation results show that the proposed algorithm has the lower complexity compared to the sphere decoding for channel matrices having low condition numbers. For further complexity reduction, we propose to use scaling, lattice-reduction, and regularization techniques. By applying these techniques, the computational complexity of proposed algorithm is reduced significantly when the channel matrix has a high condition number. [ABSTRACT FROM AUTHOR]

This paper presents a novel concept of the reversible integer discrete Fourier transform (RiDFT) of order 2r, r > 2, when the transform is split by the paired representation into a minimum set of short transforms, i.e., transforms of orders 2k, k < r. By means of the paired transform the signal is represented as a set of short signals which carry the spectral information of the signal at specific and disjoint sets of frequencies. The paired transform-based fast Fourier transform (FFT) involves a few operations of multiplication that can be approximated by integer transforms. Examples of 1-point transforms with one control bit are described. Control bits allow us to invert such approximations. Two control bits are required to perform the 8-point RiDFT, and 12 (or even 8) bits for the 16-point RiDFT of real inputs. The proposed forward and inverse RiDFTs are fast, and the computational complexity of these transforms is comparative with the complexity of the FFT. The 8-point direct and inverse RiDFTs are described in detail. [ABSTRACT FROM AUTHOR]

This paper presents a general class of fast algorithms for computing the polynomial time-frequency transform (PTFT) of length-aPb, where a, b, and p are positive integers. The process of derivation shows some interesting properties that are effectively used for minimization of the computational complexity. By assigning values of a, b, and p, various algorithms, for example, radix-a and split-radix-2/(2a), can be easily obtained to provide the flexibility supporting polynomial time-frequency transforms of various sequence lengths. The detailed analysis on the computational complexities needed by these algorithms is also presented in terms of the numbers of additions and multiplications. It is shown that the proposed algorithms significantly reduce the computational complexity for applications that deal with polynomial phase signals. [ABSTRACT FROM AUTHOR]

This paper considers the joint design of the transmitter and the receiver for linear multiple-input multiple-output (MIMO) channels when the channel state information (CSI) is available at both sides of the link. Assuming that the data symbols are mapped into points of fixed signal constellations, a transceiver structure employing widely linear (WL) filters, rather than linear ones, is proposed in order to exploit the statistical redundancy of some constellations, i.e., the correlation between the signals and their conjugate version. WL filters linearly and independently process both the in-phase and the quadrature components of the input signals and, with a limited increase in the computational complexity, allows one to improve the system performances. It is shown that, by representing the basic system model in terms of in-phase and quadrature components, the proposed structure can be derived by utilizing the already existing procedure for the design of the linear transceiver according to the minimum-mean-square-error (MMSE) criterion. The performances of the WL and linear transceivers are compared in terms of mean-square error, symbol error rate, and achieved multiplexing gain. [ABSTRACT FROM AUTHOR]

Maximum a posteriori probability (MAP) decoding of Huffman-equivalent variable-length codes (VLCs) has two undesired features. One is the high decoding complexity, and the other is the discrepancy between the objective of MAP decoding and the Levenshtein distance which is commonly used as the performance metric. In this correspondence, improvement over these two issues is targeted through extracting self-synchronization information in VLC coded sequence and incorporating it into MAP decoding. It will be shown that self-synchronization strings (SSSs) are concatenation of Huffman codewords and can be readily found. Occurrence probabilities of SSSs are then analyzed. By using this self-synchronization information, MAP decoding is split into multiple decoding of short data segments so that both decoding performance improvement and complexity reduction are obtained. Simulation results demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This correspondence investigates the Abel bound in order to predict the estimators mean square error (mse) threshold effect. A tractable and computationally efficient form of this bound is derived. This form combines the Chapman-Robbins and the Crameacuter-Rao bounds. This bound is applied to a data-aided carrier frequency estimation problem for which a closed-form expression is provided. An indicator of the signal-to-noise ratio threshold is proposed. A comparison with recent results on the Barankin bound (Chapman-Robbins version) shows the superiority of the Abel-bound version to predict the mse threshold without increasing the computational complexity [ABSTRACT FROM PUBLISHER]

This paper proposes an efficient adaptive realization of the Wiener model for the identification of complex-valued nonlinear systems. Using a two-dimensional simplicial canonical piecewise linear filter for the complex-valued nonlinear mapping, we derive a realization of the Wiener model requiring fewer parameters than previous approaches. An adaptive implementation of the proposed Wiener model is derived, and local convergence analysis for the updating algorithm is presented. The tradeoff between computational complexity and modeling performance is discussed. Simulations of a system identification example show that the proposed algorithm can provide similar or better performance than other approaches in terms of computational complexity, convergence speed, and final mean-squared error (MSE). [ABSTRACT FROM AUTHOR]

This paper describes a transform coding technique based on M-channel perfect reconstruction filter banks with a nonlinear phase. In contrast with linear-phase filter banks, the nonlinearity provides an extra degree of freedom that can be used to design a more efficient transform. We present new lattice structures of paraunitary and perfect reconstruction (biorthogonal) filter banks, which can be implemented with a lower computational complexity and/or represented by a few free parameters, through the decomposition of the lattice blocks and the displacement across the delay block. We further discuss a smooth extension method for nonlinear-phase filter banks to obtain a nonexpansive transform. The promise of our proposed approaches is demonstrated through several design examples, extended signals and compression results. [ABSTRACT FROM AUTHOR]

An adaptive receiver based on hybrid system theory is developed for a multiuser multiple-input multiple-output (MIMO) fading code-division multiple-access (CDMA) system. The basic idea is to treat the transmitted symbols and channel gains as unknown states (discrete and continuous) within a hybrid systems framework. The Bayesian-inference-based state estimation is derived using multiple model theory resulting in an optimal joint sequence estimator, which is shown to be intractable in its computational complexity. A suboptimal receiver (IMM-SIC) is then derived based on the well-known Interacting Multiple Model (IMM) algorithm and successive interference cancellation (SIC) scheme. This paper shows the specific approximations made to the probability densities of the optimal receiver in deriving the IMM-SIC receiver with complexity linear in number of users. This receiver design is well suited for online recursive processing of space-time coded CDMA system, where the decoding stage is incorporated within the multiple model framework. [ABSTRACT FROM AUTHOR]

In this paper, a robust watermarking algorithm using balanced multiwavelet transform is proposed. The latter transform achieves simultaneous orthogonality and symmetry without requiring any input prefiltering. Therefore, considerable reduction in computational complexity is possible, making this transform a good candidate for real-time watermarking implementations such as audio broadcast monitoring and DVD video watermarking. The embedding scheme is image adaptive using a modified version of a well-established perceptual model. Therefore, the strength of the embedded watermark is controlled according to the local properties of the host image. This has been achieved by the proposed perceptual model, which is only dependent on the image activity and is not dependent on the multifilter sets used, unlike those developed for scalar wavelets. This adaptivity is a key factor for achieving the imperceptibility requirement often encountered in watermarking applications. In addition, the watermark embedding scheme is based on the principles of spread-spectrum communications to achieve higher watermark robustness. The optimal bounds for the embedding capacity are derived using a statistical model for balanced multiwavelet coefficients of the host image. The statistical model is based on a generalized Gaussian distribution. Limits of data hiding capacity clearly show that balanced multiwavelets provide higher watermarking rates. This increase could also be exploited as a side channel for embedding watermark synchronization recovery data. Finally, the analytical expressions are contrasted with experimental results where the robustness of the proposed watermarking system is evaluated against standard watermarking attacks. [ABSTRACT FROM AUTHOR]

Recently, a novel maximum-likelihood sequence estimation (MLSE) equalizer was reported that avoids the explicit estimation of the channel impulse response. Instead, it is based on the fact that the (noise-free) channel outputs, needed by the Viterbi algorithm, coincide with the points around which the received (noisy) samples are clustered and can thus be estimated directly with the aid of a supervised clustering method. Moreover, this is achieved in a computationally efficient manner that exploits the channel linearity and the symmetries underlying the transmitted signal constellation. The resulting computational savings over the conventional MLSE equalization scheme are significant even in the case of relatively short channels where MLSE equalization is practically applicable. It was demonstrated, via simulations, that the performance of this algorithm is close to that using a least-squares (LS) channel estimator, although its computational complexity is even lower than that of the least-mean squares (LMS)-trained MLSE equalizer. This paper investigates the relationship of the center estimation (CE) part of the proposed equalizer with the LS method. It is proved that, when using LS with the training sequence employed by CE, the two methods lead to the same solution. However, when LS is trained with random data, it outperforms CE, with the performance difference being proportional to the channel length. A modified CE method, called MCE, is thus developed, that attains the performance of LS with perfectly random data, while still being much simpler computationally than classical LS estimation. Through the results of this paper, CE is confirmed as a method- ology that combines high performance, simplicity, and low computational cost, as required in a practical equalization task. An alternative, algebraic viewpoint on the CE method is also provided. [ABSTRACT FROM AUTHOR]

The FastICA or fixed-point algorithm is one of the most successful algorithms for linear independent component analysis (ICA) in terms of accuracy and computational complexity. Two versions of the algorithm are available in literature and software: a one-unit (deflation) algorithm and a symmetric algorithm. The main result of this paper are analytic closed-form expressions that characterize the separating ability of both versions of the algorithm in a local sense, assuming a ‘good’ initialization of the algorithms and long data records. Based on the analysis, it is possible to combine the advantages of the symmetric and one-unit version algorithms and predict their performance. To validate the analysis, a simple check of saddle points of the cost function is proposed that allows to find a global minimum of the cost function in almost 100% simulation runs. Second, the Cramér-Rao lower bound for linear ICA is derived as an algorithm independent limit of the achievable separation quality. The FastICA algorithm is shown to approach this limit in certain scenarios. Extensive computer simulations supporting the theoretical findings are included. [ABSTRACT FROM AUTHOR]

This paper proposes a new second-order statistics-based method for blind multiple-input multiple-output (MIMO) finite-impulse-response (FIR) channel estimation driven by colored sources. It is assumed that the second-order statistics (SOS) of the input sources are known a priori. By exploiting the new derived properties of the companion matrices, an original proof for the uniqueness of the system solution is provided, which serves as a theoretical basis for the proposed new method that admits a closed-form solution. The corresponding identifiability conditions and the computational complexity of the proposed method are discussed and compared with other existing method. Numerical simulation results are presented to illustrate the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we develop some new automatic repeat request (ARQ) protocols for multiple-input multiple-out (MIMO) flat-fading channels which adapt the bit-to-symbol mapping of each ARQ retransmission. We begin by defining a model for distinctly mapped transmissions through flat-fading MIMO channels. We characterize the effect that such a mapping diversity has on an integrated receiver utilizing sphere decoding. Varying the symbol mapping complicates the sphere decoding process, particularly for the enumeration of candidate solutions within the sphere. A technique that enables quick candidate enumeration is presented, utilizing concepts from existing closest point search schemes. The advantage of mapping diversity, in reducing bit error rate and reducing computational complexity, is presented along with simulation examples. [ABSTRACT FROM AUTHOR]

This correspondence proposes a new block-exact fast least-mean squares (LMS)/Newton algorithm for adaptive filtering. It is obtained by exploiting the shifting property of the whitened input of the fast LMS/Newton algorithm so that a block-exact update can be carried out in the LMS part of the algorithm. The proposed algorithm has significantly less computational complexity than, but exact mathematical equivalence to, the fast LMS/Newton algorithm! Since short block length is allowed, the processing delay introduced is not excessively large as in conventional block filtering generalization. Implementation issues and the experimental results are given to illustrate the principle and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of channel estimation for direct-sequence code-division multiple-access (DS-CDMA) systems with time-varying multipath fading channels. The multi- path fading channels are modeled as autoregressive (AR) models. A method is first proposed to convert the time-varying regression model due to the time-varying nature of users' information symbols into a time-invariant one. Then, a polynomial approach is pro- posed to obtain the minimum mean square error (MMSE) estimator. The uncertainty of the channel model and decision errors of the DS-CDMA detector are taken into consideration in the design of the MMSE estimator. Compared with the Kalman estimator, the computational complexity of the proposed algorithm is much lower. The simulation results show that the proposed estimator provides a comparable estimation performance with the Kalman estimator and is robust for fast-fading channels. [ABSTRACT FROM AUTHOR]

This paper proposes low-complexity constrained affine-projection (CAP) algorithms. The algorithms are suitable for linearly constrained filtering problems often encountered in communications systems. The CAP algorithms derived in this paper trade convergence speed and computational complexity in the same way as the conventional afilne-projection (AP) algorithm. In addition, data-selective versions of the CAP algorithm are derived based on the concept of set-membership filtering. The set-membership constrained affine-projection (SM-CAP) algorithms include several constraint sets in order to construct a space of feasible solutions for the coefficient updates. The SM-CAP algorithms include a data-dependent step size that provides fast convergence and low mean-squared error. The paper also discusses important aspects of convergence and stability of constrained normalized adaptation algorithms and shows that normalization may introduce bias in the final solution. [ABSTRACT FROM AUTHOR]

In this paper, the computational complexity of the marginalized particle filter is analyzed and a general method to perform this analysis is given. The key is the introduction of the equivalent flop measure. In an extensive Monte Carlo simulation, different computational aspects are studied and compared with the derived theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, a fast approximate inverse-power (AIP) iteration is applied to compute recursively the total least squares (TLS) solution for unbiased equation-error adaptive infinite impulse response (IIR) filtering, which is established by approximating the well-known inverse-power iteration with Galerkin method. The AIP algorithm is based on an interesting modification of the inverse-power iteration in which the first entry of the parameter vector is constrained to the negative one. The distinctive feature of the proposed algorithm lies in its high computational efficiency, which is characterized by efficient computation of the fast gain vector (FGV), adaptation of the interesting modification of the inverse-power iteration, and rank-one update of the augmented correlation matrix. The shift structure of the input data vector is exploited to develop a fast algorithm for computing the gain vector. This FGV algorithm can be implemented at a numerical cost lower than the well-known fast Kalman algorithm. Since the first entry of the parameter vector has been fixed as the negative one and the weight vector is updated along the input data vector, a very efficient AIP algorithm is obtained by using the FGV algorithm. The proposed AIP algorithm is of computational complexity O(L) per iteration. Moreover, with no need to use the well-known matrix-inversion lemma, the AIP algorithm has another attractive feature of numerical stability. The proposed algorithm is shown to have global convergence. Simulation examples are included to demonstrate the effectiveness of the proposed AIP algorithm. [ABSTRACT FROM AUTHOR]

We consider a general method for constructing dual Gabor elements different from the canonical dual. Our approach is based on combining two Gabor frames such that the generated frame-type operator Sg,γ is nonsingular. We provide necessary and sufficient conditions on the Gabor window functions g and γ such that Sg,γ is nonsingular for rational oversampling, considering both the continuous-time and the discrete-time settings. In contrast to the frame operator, the operator Sg,γ is, in general, not positive. Therefore, all results in Gabor analysis that are based on the positivity of the frame operator cannot be applied directly. The advantage of the proposed characterization is that the algebraic system for computing the Gabor dual elements preserves the high structure of usual Gabor frames, leading to computationally efficient algorithms. In particular, we consider examples in which both the condition number and the computational complexity in computing the proposed dual Gabor elements decrease in comparison to the canonical dual Gabor elements. [ABSTRACT FROM AUTHOR]

To ease equalization in a multicarrier system, a cyclic prefix (CP) is typically inserted between successive symbols. When the channel order exceeds the CP length, equalization can be accomplished via a time-domain equalizer (TEQ), which is a finite impulse response (FIR) filter. The TEQ is placed in cascade with the channel to produce an effective shortened impulse response. Alternatively, a bank of equalizers can remove the interference tone-by-tone. This paper presents a unified treatment of equalizer designs for multicarrier receivers, with an emphasis on discrete multitone systems. It is shown that almost all equalizer designs share a common mathematical framework based on the maximization of a product of generalized Rayleigh quotients. This framework is used to give an overview of existing designs (including an extensive literature survey), to apply a unified notation, and to present various common strategies to obtain a solution. Moreover, the unification emphasizes the differences between the methods, enabling a comparison of their advantages and disadvantages. In addition, 16 different equalizer structures and design procedures are compared in terms of computational complexity and achievable bit rate using synthetic and measured data. [ABSTRACT FROM AUTHOR]

This paper considers the problem of simultaneous multiuser downlink beamforming. The idea is to employ a transmit antenna array to create multiple "beams" directed toward the individual users, and the aim is to increase throughput, measured by sum capacity. In particular, we are interested in the practically important case of more users than transmit antennas, which requires user selection. Optimal solutions to this problem can be prohibitively complex for online implementation at the base station and entail so-called Dirty Paper (DP) precoding for known interference. Suboptimal solutions capitalize on multiuser (selection) diversity to achieve a significant fraction of sum capacity at lower complexity cost. We analyze the throughput performance in Rayleigh fading of a suboptimal greedy DP-based scheme proposed by Tu and Blum. We also propose another user-selection method of he same computational complexity based on simple zero-forcing beamforming. Our results indicate that the proposed method attains a significant fraction of sum capacity and throughput of Tu and Blum's scheme and, thus, offers an attractive alternative to DP-based schemes. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of two-dimensional (2-D) adaptive array beamforming with multiple beam constraints (MB C) using a generalized sidelobe canceller (GSC). We present a method for the construction of signal blocking matrix required by the 2-D GSC. The resulting 2-D adaptive beamformer can provide almost the same performance as conventional 2-D adaptive beamformers based on a lineally constrained minimum variance (LCMV) criterion. The effectiveness of the proposed GSC is that the construction of the required signal blocking matrix requires only the computation of a few entries from analytical formulas. In comparison with conventional methods, the proposed technique gets rid of the computational complexity due to the eigendecomposition required for finding the 2-D signal blocking matrix. For dealing with the performance degradation due to coherent interference, we present a 2-D weighted spatial smoothing scheme to effectively alleviate the coherent jamming effect. Several simulation examples are provided for illustration and comparison. [ABSTRACT FROM AUTHOR]

In this paper, we first propose an efficient algorithm for computing one-dimensional (1-D) discrete cosine transform (DCT) for a signal block, given its two adjacent sub blocks in the DCT domain and then introduce several algorithms for the fast computation of multidimensional (m-D) DCT with size N1 × N2 ×…× Nm given 2m subblocks of DCT coefficients with size N1/2 × N2/2 ×… × Nm/2, where Ni(i=1,2,ߪ,m) are powers of 2. Obviously, the row-column method, which employs the most efficient algorithms along each dimension, reduces the computational complexity considerably, compared with the traditional method, which employs only the one-dimensional (1-D) fast DCT and inverse DCT (IDCT) algorithms. However, when m & 2, the traditional method, which employs the most efficient multidimensional DCT/IDCT algorithms, has lower computational complexity than the row-column method. Besides, we propose a direct method by dividing the data into 2m parts for independent fast computation, in which only two steps of r-dimensional (r = 1,2,…, m) IDCT and additional multiplications and additions are required. If all the dimensional sizes are the same, the number of multiplications required for the direct method is only (2m - 1)/m2m-1 times of that required for the row-column method, and if N & 22m-1, the computational efficiency of the direct method is surely superior to that of the traditional method, which employs the most efficient multidimensional DCT/DCT algorithms. [ABSTRACT FROM AUTHOR]

This paper introduces a fast implementation of the power iteration method for subspace tracking, based on an approximation that is less restrictive than the well-known projection approximation. This algorithm, referred to as the fast approximated power iteration (API) method, guarantees the orthonormality of the subspace weighting matrix at each iteration. Moreover, it out-performs many subspace trackers related to the power iteration method, such as PAST, NIC, NP3, and OPAST, while having the same computational complexity. The API method is designed for both exponential windows and sliding windows. Our numerical simulations show that sliding windows offer a faster tracking response to abrupt signal variations. [ABSTRACT FROM AUTHOR]