The ubiquity of wireless connectivity between an ever-increasing number of devices has confirmed dire past predictions of widespread eavesdropping (among other security concerns) in wireless networks, further promoting the need for secure communications. Of particular interest are physical layer techniques which exploit error-correction coding intrinsic to digital transceivers and which offer two clear advantages: (i) no need for key distribution; and (ii) secrecy that is not conditioned on a computationally limited adversary. Present techniques, however, assume some knowledge of the channel connecting the transmitter to the eavesdropper; if the eavesdropper is truly passive, this critical parameter is unavailable. We therefore examine secure communication schemes that do not assume knowledge of the eavesdropper's channel, yet remain keyless in their operation. Two schemes are offered, with behavior intermediate between cryptographic and information-theoretic solutions.

The articles in this special issue highlight recent advances along with the remaining challenges in the field of physical-layer communications security.

Consider a message coded for storage in which a fraction of the stored data is stolen. Ideally, the data remaining should allow message recovery, while the stolen data should reveal no information on the message. This gives a twist on the erasure wiretap channel, in that “Bob” no longer has a clear channel from “Alice”. We show how the storage capacity can, as in other multi-terminal coding problems, be approached using nested codes, and propose nested erasure codes using Krylov subspaces. These offer good performance and perfect secrecy, while integrating the nested code structure naturally.

Sensor localization typically exploits distance measurements to infer sensor positions with respect to known anchor nodes. Missing or unreliable measurements for specific nodes can impede such procedures, raising the problem of distance measurement reconstruction using distance information from other nodes. Here we develop further structural features of matrices of pairwise distances, as inherited from the classical multidimensional scaling problem. We show in particular an inertial property which can be successfully exploited to overcome inconsistencies that result in certain cases from an earlier approach of. We likewise develop linear algebraic solutions to the missing distance problem.

A complex adaptive notch filter is developed, for tracking single-sided (a.k.a. analytic or complex) tones immersed in background noise. A complex all-pass based realization is pursued which inherits useful properties from its real counterpart: independent tuning of the notch frequency and attenuation bandwidth, easy realization of the complementary band-pass filter, unbiased frequency estimation, and faster convergence and tracking than a gradient descent algorithm.

Belief propagation, via a novel reinterpretation of the Bethe free energy's pseudo-dual, is shown to be related to a novel relaxation of maximum likelihood detection via a constrained optimization. The conventional maximum likelihood detection falls out for a zero constraint, and belief propagation's fixed points are obtained for other constraint values.

Belief propagation is shown to be an instance of a hybrid between two projection algorithms in the convex programming literature: Dykstra's algorithm with cyclic Bregman projections and an alternating Bregman projections algorithm. Via this connection, new results concerning the convergence and performance of belief propagation can be proven by exploiting the corresponding literature about the two projections algorithms it hybridizes. In this regard, it is identified that the lack of guaranteed convergence for belief propagation results from the asymmetry of its Bregman divergence by proving that when the associated hybrid projection algorithm generalization is used with a symmetric Bregman divergence, it always converges. Additionally, by characterizing factorizations that are close to acyclic in a manner independent of their girth, a new collection of distributions for which belief propagation is guaranteed to perform well is identified using the new projection algorithm framework.

Modern coding advances, including dirty paper coding and information hiding, require quantizing a given binary word to a code word. A 'good' solution would approach the rate-distortion bound in lossy source compression. Here we propose a simple variant on belief propagation which is observed to converge to a solution giving respectable rate-distortion performance. Comparisons with other recently proposed source quantization methods reveal that the proposed algorithm holds particular interest in short block-length applications, as encountered in packet-based communication systems.

Recent information hiding schemes are scrutinized in terms of their cryptographic performance. We establish conditions under which the key equivocation function is optimal for the studied schemes, and show that, under a reasonable key generation model, the perfect secrecy property is nearly satisfied, limited by a mutual information measure that decreases exponentially with the block length. The novelty of the work is to extend classical cryptographic analysis results to schemes involving cover signals, a component absent from standard cryptography. The schemes show unexpectedly good cryptographic security, although we observe that information embedding with robustness has steganographic weaknesses.

The estimation error performance of Gaussian belief propagation based distributed estimation in a large sensor network employing random sleep strategies is explicitly evaluated for a simple model using density evolution analysis. Both regular sleep strategies, in which the number of nodes awake at any time instant is fixed, as well as irregular sleep strategies, in which the number of awake nodes may vary, are analyzed. The calculated estimation error is used to study the tradeoff between estimation accuracy and energy consumption, as well as to dictate the optimal parameters for the random sleep strategy.

Some information-hiding schemes are scrutinized in terms of their cryptographic secrecy. The schemes under study appeal to the so-called matrix embedding strategy, designed to optimize embedding capacity under distortion constraints, as opposed to any cryptographic measure. Nonetheless, we establish conditions under which a key equivocation function is optimal, and show that under reasonable key generation models, a perfect secrecy property is nearly satisfied, limited by a mutual information measure that decreases exponentially with the block length.

The near-optimal performance of the turbo decoder has been a source of intrigue among communications engineers and information theorists, given itsad hocorigins that were seemingly disconnected from optimization theory. Naturally one would inquire whether the favorable performance might be explained by characterizing the turbo decoder via some optimization criterion or performance index. Recently, two such characterizations have surfaced. One draws from statistical mechanics and aims to minimize the Bethe approximation to a free energy measure. The other characterization involves constrained likelihood estimation, a setting perhaps more familiar to communications engineers. The intent of this paper is to assemble a tutorial overview of these recent developments, and more importantly to identify the formal mathematical duality between the two viewpoints. The paper includes tutorial background material on the information geometry tools used in analyzing the turbo decoder, and the analysis accommodates both the parallel concatenation and serial concatenation schemes in a common framework.

Expectation propagation defines a family of algorithms for approximate Bayesian statistical inference which generalize belief propagation on factor graphs with loops. As is the case for belief propagation in loopy factor graphs, it is not well understood why the stationary points of expectation propagation can yield good estimates. In this paper, given a reciprocity condition which holds in most cases, we provide a constrained maximum likelihood estimation problem whose critical points yield the stationary points of expectation propagation. Expectation propagation may then be interpreted as a nonlinear block Gauss Seidel method seeking a critical point of this optimization problem

The turbo decoder was not originally introduced as a solution to an optimization problem, which has impeded attempts to explain its excellent performance. Here it is shown, that the turbo decoder is an iterative method seeking a solution to an intuitively pleasing constrained optimization problem. In particular, the turbo decoder seeks the maximum-likelihood sequence (MLS) under the false assumption that the input to the encoders are chosen independently of each other in the parallel case, or that the output of the outer encoder is chosen independently of the input to the inner encoder in the serial case. To control the error introduced by the false assumption, the optimizations are performed subject to a constraint on the probability that the independent messages happen to coincide. When the constraining probability equals one, the global maximum of the constrained optimization problem is the maximum-likelihood sequence detection (MLSD), allowing for a theoretical connection between turbo decoding and MLSD. It is then shown that the turbo decoder is a nonlinear block Gauss-Seidel iteration that aims to solve the optimization problem by zeroing the gradient of the Lagrangian with a Lagrange multiplier of -1. Some conditions for the convergence for the turbo decoder are then given by adapting the existing literature for Gauss-Seidel iterations

Previous results based on balanced realization theory and concerning the local convergence speed of adaptive IIR filters apply to the sufficient order case. In the undermodelled case, situations of greater practical interest are those in which the order chosen for the adaptive filter provides a good approximation of the system being modelled. A relevant question is then if the existence of a good approximation of the system implies a good approximation of the sufficient order convergence speed properties. We address this problem here, based on the same balanced realization theory framework. Our results suggest a positive answer to the question.

Many previous attempts at analyzing the convergence behavior of turbo and iterative decoding, such as EXIT style analysis (ten Brink, S., 2001) and density evolution (El Gamal, H. and Hammons, A.R., Jr, 2001), ultimately appeal to results which become valid only when the block length grows rather large, while still other attempts, such as connections to factor graphs (Kshischang, F.R. et al., 2001) and belief propagation (McEliece, R.J., 1998), have been largely unsuccessful at showing convergence due to loops in the turbo coding graph. The paper presents an information geometric interpretation which, built on the results of M. Moher and T. A. Gulliver (IEEE Trans. Inform. Theory, vol.4, p.3097-104, 1998), S. Ikeda et al. (IEEE Trans. Inform. Theory, vol.50, p.1097-114, 2004), and T. Richardson (IEEE Trans. Inform. Theory, vol.46, p.9-23, 2000), allows us to relate the quantities of interest in the turbo decoder. Using it, we point out a measure which is key in studying convergence.

Many previous attempts at analyzing the convergence behavior of turbo and iterative decoding, such as EXIT style analysis (S. ten Brink, Oct. 2001) and density evolution (H. El Gamal and A. R. Hammons, Jr, Feb. 2001), ultimately appeal to results which become valid only when the block length grows rather large, while still other attempts, such as connections to factor graphs (F. R. Kshischang, et al., Feb. 2001) and belief propagation (R. J. McEliece, et al., Feb. 1998), have been largely unsuccessful at showing convergence due to loops in the turbo coding graph. The information geometric attempts (M. Moher and T. A. Gulliver, Nov. 1998), (T. Richardson, Jan. 2000), (S. Ikeda, et al., June 2004), (B. Muquest, et al., June 2002), and (J. Walsh, et al., March 2005), in turn have been inhibited by inability to efficiently describe intrinsic information extraction as an information projection. This paper recognizes turbo decoding as an instance of a Gauss-Seidel iteration on a particular nonlinear system of equations. This interpretation holds regardless of block length, and allows a connection to existing convergence results for nonlinear block Gauss Seidel iterations. We thus adapt existing convergence theory for the Gauss Seidel iteration to give sufficient conditions for the convergence of the turbo decoder that hold regardless of the block length

A parameterization of an adaptive IIR filter's poles is developed, based on balanced realization theory. From this we develop a local approximation of the actual adapted pole parameters, in which convergence speed is related to a certain eigenvalue spread. This, in turn, is shown to relate to the Hankel singular values of the system to be identified, as well as certain coefficient sensitivity functions of the adapted filter. Based on these properties, a new adaptive IIR algorithm is proposed. In order to achieve faster convergence, it combines an adaptive lattice with function approximation.

The turbo decoding algorithm has met with intense study over the past decade, in an attempt to harness the full power of the "turbo principle". Here we consider applying contractivity arguments to the turbo decoding algorithm, to study convergence even for short block lengths.

We re-examine a fixed-point algorithm proposed by Hyvarinen for independent component analysis, wherein local convergence is proved subject to an ideal signal model using a square invertible mixing matrix. Here, we derive step-size bounds which ensure monotonic convergence to a local extremum for any initial condition. Our analysis does not assume an ideal signal model but appeals rather to properties of the contrast function itself, and so applies even with noisy data and/or more sources than sensors. The results help alleviate the guesswork that often surrounds step-size selection when the observed signal does not fit an idealized model.

A finite-interval constant modulus algorithm is developed which is vastly simpler than the Analytic Constant Modulus Algorithm and, unlike that algorithm, can claim to minimize a constant modulus criterion. It requires one QR decomposition of a data matrix, followed by a power iteration. Step size bounds which ensure monotonic convergence are obtained in analytic form, and proper tuning leads to an algorithm which converges typically within a few iterations. The algorithm thus gives a computationally feasible method for implementing constant modulus signal restoration in packet-based transmission systems.

We study the asymptotic behavior of the smallest singular value of the single input multiple output (SIMO) channel filtering matrix. We prove that this can be expressed in terms of the sub-channel transfer functions. We apply this result to study the identifiability of bandlimited channels from their (estimated) second order statistics (SOS). We prove, and verify through examples, that SOS based algorithms are unable to identify frequency selective channels regardless of the assumed channel order.

Szego's (1984) theorem states that the asymptotic behavior of the eigenvalues of a Hermitian Toeplitz matrix is linked to the Fourier transform of its entries. This result was later extended to block Toeplitz matrices, i.e., covariance matrices of multivariate stationary processes. The present work gives a new proof of Szego's theorem applied to block Toeplitz matrices. We focus on a particular class of Toeplitz matrices, those corresponding to covariance matrices of single-input multiple-output (SIMO) channels. They satisfy some factorization properties that lead to a simpler form of Szego's theorem and allow one to deduce results on the asymptotic behavior of the lowest nonzero eigenvalue for which an upper bound is developed and expressed in terms of the subchannels frequency responses. This bound is interpreted in the context of blind channel identification using second-order algorithms, and more particularly in the case of band-limited channels.

Active research in blind identification of single input multiple output (SIMO) channels has led to a variety of second order statistics based algorithms, mainly the subspace and the linear prediction approaches. The subspace algorithm shows good performance, although it requires exact knowledge of the channel order, which is not guaranteed by current order detection algorithms. The linear prediction algorithm is sensitive to observation noise while its robustness to channel order over estimation is only theoretical. We propose a new second order statistics based blind channel identification algorithm using a shifted version of the channel output covariance matrix. It proves to be truly robust to channel order over estimation i.e., able to estimate the channel impulse response when the assumed channel order is greater than the exact order and when channel output is corrupted by additive noise and observed over finite time duration. Moreover, the proposed algorithm shows clearly better performance than the linear prediction algorithm.

We revisit the higher-order power method of De Lathauwer et al. (1995) for rank-one tensor approximation, and its relation to contrast maximization as used in blind deconvolution. We establish a simple convergence proof for the general nonsymmetric tensor case. We show also that a symmetric version of the algorithm, offering an order of magnitude reduction in computational complexity but discarded by De Lathauwer et al. as unpredictable, is likewise provably convergent. A new initialization scheme is also developed which, unlike the TSVD-based initialization, leads to a quantifiable proximity to the globally optimal solution.

This article reviews the super-exponential algorithm proposed by Shalvi and Weinstein (1993) for blind channel equalization. The principle of this algorithm-Hadamard exponentiation, projection over the set of attainable combined channel-equalizer impulse responses followed by a normalization-is shown to coincide with a gradient search of an extremum of a cost function. The cost function belongs to the family of functions given as the ratio of the standard l/sub 2p/ and l/sub 2/ sequence norms, where p>1. This family is very relevant in blind channel equalization, tracing back to Donoho's (1981) work on minimum entropy deconvolution and also underlying the Godard (1980) (or constant modulus) and the earlier Shalvi-Weinstein algorithms. Using this gradient search interpretation, which is more tractable for analytical study, we give a simple proof of convergence for the super-exponential algorithm. Finally, we show that the gradient step-size choice giving rise to the super-exponential algorithm is optimal.

This paper reviews the super-exponential algorithm proposed by Shalvi and Weinstein (1993) for blind channel equalization. We show that the algorithm coincides with a gradient search of a maximum of a cost function, which belongs to a family of functions very relevant in blind channel equalization. This family traces back to Donoho's (1981) work on minimum entropy deconvolution, and also underlies the Godard (1980) (or constant modulus) and the Shalvi-Weinstein algorithms. Using this gradient search interpretation, we give a simple proof of convergence for the super-exponential algorithm. Finally, we show that the gradient step-size choice giving rise to the super-exponential algorithm is optimal.

The continuous use of adaptive algorithms is strongly dependent on their behavior in finite-precision environments. We study the nonlinear round-off error accumulation system of the conventional RLS algorithm and we derive bounds for the relative precision of the computations and the accumulated round-off error, which guarantee the numerical stability of the finite-precision implementation of the algorithm. The bounds depend on the conditioning of the problem and the exponential forgetting factor. Simulations agree with our theoretical results.

This paper compares the eigenstructure and modulation algorithms, which are used for two-channel lossless FIR filter optimization. We study the effects of eigenvalue separation of the input covariance matrix and the step size on their convergence behavior. First, we show that the convergence rate of two algorithms increases as the separation of eigenvalues of the covariance matrix increases. The modulation algorithm converges more rapidly than the eigenstructure one because of its better eigenvalue separation. Second, the necessary condition for which the two algorithms converge is derived. Simulations are presented which support the analysis.

We establish the existence of asymptotic stationary points for a class of adaptive IIR filtering algorithms, including (S)HARF, the Feintuch (1996) algorithm, and Landau's (1976) algorithm, for reduced-order cases. We show first that the nonlinear equations characterizing a stationary point admit a solution giving rise to a stable transfer function, when the input is white noise. We then show that an analytic procedure to construct the solution may be reduced to the Nevanlinna-Pick interpolation problem. The white noise assumption on the input simplifies the mathematics of an already difficult problem, although the existence proof appears extendable to correlated inputs as well.

We consider the problem of adaptively optimizing a two-channel lossless FIR filter bank, which finds application in subband coding or wavelet signal analysis. Instead of using a gradient descent procedure-with its inherent problem of possible convergence to local minima-we consider two eigenstructure algorithms. Both algorithms feature a priori bounds on the output error variance at any convergent point, and based on simulations lead to solutions that lie acceptably close to a global minimum point of an output error cost function.

Least-squares equation-error models are widely used as a simple means of estimating an input-output transfer function in a system identification context.. Although the models furnished by the least-squares method are not always stable, some recent works have shown that an autoregressive constraint on the input is sufficient to ensure stability of the furnished model. Here we provide a simple proof of this property for multivariable system estimation.>

A recently proposed adaptive orthogonal subspace filter is specialized to the two-channel case, resulting in a subspace system identification algorithm. In addition to the standard benefits of orthogonal-based adaptive IIR filters-inherent stability of the filter structure even with time variation in the parameters, and robust performance in finite precision environments-the proposed method allows the identification of noncausal components using a causal filtering method. Moreover, the estimation algorithm is unbiased with respect to white noise in both the input and output sequences of the system to be identified, unlike previous approaches which are unbiased with respect to output noise alone. An a posteriori based algorithm is derived, which enjoys superior convergence properties over a previous a priori based algorithm.>

The estimation problem for rational-type spectral signal subspaces in the time domain is discussed. Two methods are presented. The first is the transcription of the methods proposed by K.M. Buckley and L.J. Griffiths (1988) to the rational modeling context. It is based on the fact that a one-to-one correspondence exists between the polynomial vector-valued functions of the noise spectral subspace and the eigenspace corresponding to the smallest eigenvalue of the covariance matrix of the data. In the second method, the authors exploit the fact that the noise spectral subspace admits rational-type orthonormal bases related to the causal rational transfer functions with coisometric values on the unit circle, the action of which on the data produces a minimum energy output. This optimization problem is solved by using an efficient parametrization of these transfer functions in conjunction with a gradient algorithm, the initial conditions of which are calculated by using the first method. By contrast with the first approach, it is shown that the corresponding estimator is related to a quadratic reconstruction criterion which can be interpreted as a maximum-likelihood criterion in a particular case.>

The fact that lattice and QR methods of adaptive least-squares filtering follow from the same geometric framework allows the first solution to the parameter identification problem using fast QR techniques. These relations suggest combining QR and lattice algorithms into hybrid algorithms of low complexity and good numerical behavior. It is emphasized that many other possibilities are available for mixing and matching the steps of QR and lattice algorithms. The various algorithms so obtained differ in their computational complexity, accessibility to desired variables, etc., but all work within a related geometric framework.>

The properties of digital all-pass filters are reviewed and a broad overview of the diversity of applications in digital filtering is provided. Starting with the definition and basic properties of a scalar all-pass function, a variety of structures satisfying the all-pass property are assembled, with emphasis placed on the concept of structural losslessness. Applications are then outlined in notch filtering, complementary filtering and filter banks, multirate filtering, spectrum and group-delay equalization, and Hilbert transformations. In all cases, the structural losslessness property induces very robust performance in the face of multiplier coefficient quantization. Finally, the state-space manifestations of the all-pass property are explored, and it is shown that many all-pass filter structures are devoid of limit cycle behavior and feature very low roundoff noise gain.>

It is shown that a wide class of real-coefficient, doubly-complementary IIR transfer-function pairs can be implemented by means of a single complex allpass filter. For a real input sequence, the real part of the output sequence of the complex allpass filter corresponds to one of the transfer functions G(z) (for example, low-pass), whereas the imaginary part of the output sequence corresponds to its "complementary" filter H(z) (for example, highpass). Since the resulting implementation is structurally lossless, G(z) and H(z) have very low passband-sensitivity. Numerical design examples are included to demonstrate the ideas.