Performance analysis of minimum /spl lscr//sub 1/-norm solutions for underdetermined source separation

Results of the analysis of the performance of minimum /spl lscr//sub 1/-norm solutions in underdetermined blind source separation, that is, separation of n sources from m(相似文献   

Convergence and loss bounds for Bayesian sequence prediction

The probability of observing x/sub t/ at time t, given past observations x/sub 1/...x/sub t-1/ can be computed if the true generating distribution /spl mu/ of the sequences x/sub 1/x/sub 2/x/sub 3/... is known. If /spl mu/ is unknown, but known to belong to a class /spl Mscr/ one can base one's prediction on the Bayes mix /spl xi/ defined as a weighted sum of distributions /spl nu/ /spl isin/ /spl Mscr/. Various convergence results of the mixture posterior /spl xi//sub t/ to the true posterior /spl mu//sub t/ are presented. In particular, a new (elementary) derivation of the convergence /spl xi//sub t///spl mu//sub t/ /spl rarr/ 1 is provided, which additionally gives the rate of convergence. A general sequence predictor is allowed to choose an action y/sub t/ based on x/sub 1/...x/sub t-1/ and receives loss /spl lscr//sub x(t)y(t)/ if x/sub t/ is the next symbol of the sequence. No assumptions are made on the structure of /spl lscr/ (apart from being bounded) and /spl Mscr/. The Bayes-optimal prediction scheme /spl Lambda//sub /spl xi// based on mixture /spl xi/ and the Bayes-optimal informed prediction scheme /spl Lambda//sub /spl mu// are defined and the total loss L/sub /spl xi// of /spl Lambda//sub /spl xi// is bounded in terms of the total loss L/sub /spl mu// of /spl Lambda//sub /spl mu//. It is shown that L/sub /spl xi// is bounded for bounded L/sub /spl mu// and L/sub /spl xi///L/sub /spl mu// /spl rarr/ 1 for L/sub /spl mu// /spl rarr/ /spl infin/. Convergence of the instantaneous losses is also proven.     

Achievable key rates for universal simulation of random data with respect to a set of statistical tests

We consider the problem of universal simulation of an unknown source from a certain parametric family of discrete memoryless sources, given a training vector X from that source and given a limited budget of purely random key bits. The goal is to generate a sequence of random vectors {Y/sub i/}, all of the same dimension and the same probability law as the given training vector X, such that a certain, prescribed set of M statistical tests will be satisfied. In particular, for each statistical test, it is required that for a certain event, /spl epsiv//sub /spl lscr//, 1 /spl les/ /spl lscr/ /spl les/ M, the relative frequency /sup 1///sub N/ /spl Sigma//sub i=1//sup N/ 1/sub /spl epsiv//spl lscr//(Y/sub i/) (1/sub /spl epsiv//(/spl middot/) being the indicator function of an event /spl epsiv/), would converge, as N /spl rarr/ /spl infin/, to a random variable (depending on X), that is typically as close as possible to the expectation of 1/sub /spl epsiv//spl lscr/,/ (X) with respect to the true unknown source, namely, to the probability of the event /spl epsiv//sub /spl lscr//. We characterize the minimum key rate needed for this purpose and demonstrate how this minimum can be approached in principle.     

Decoding by linear programming

This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.     

Cubic self-dual binary codes

We study binary self-dual codes with a fixed point free automorphism of order three. All binary codes of that type can be obtained by a cubic construction that generalizes Turyn's. We regard such "cubic" codes of length 3/spl lscr/ as codes of length /spl lscr/ over the ring F/sub 2//spl times/F/sub 4/. Classical notions of Type II codes, shadow codes, and weight enumerators are adapted to that ring. Two infinite families of cubic codes are introduced. New extremal binary codes in lengths /spl les/ 66 are constructed by a randomized algorithm. Necessary conditions for the existence of a cubic [72,36,16] Type II code are derived.     

On the filtering problem for stationary random /spl Zopf//sup 2/-fields

It is shown that whenever a stationary random field (Z/sub n,m/)/sub n,m/spl isin/z/ is given by a Borel function f:/spl Ropf//sup z/ /spl times/ /spl Ropf//sup z/ /spl rarr/ /spl Ropf/ of two stationary processes (X/sub n/)/sub n/spl isin/z/ and (Y/sub m/)/sub m/spl isin/z/ i.e., then (Z/sub n, m/) = (f((X/sub n+k/)/sub k/spl epsi/z/, (Y/sub m + /spl lscr// )/sub /spl lscr/ /spl epsi/z/)) under a mild first coordinate univalence assumption on f, the process (X/sub n/)/sub n/spl isin/z/ is measurable with respect to (Z/sub n,m/)/sub n,m/spl epsi/z/ whenever the process (Y/sub m/)/sub m/spl isin/z/ is ergodic. The notion of universal filtering property of an ergodic stationary process is introduced, and then using ergodic theory methods it is shown that an ergodic stationary process has this property if and only if the centralizer of the dynamical system canonically associated with the process does not contain a nontrivial compact subgroup.     

Entropy and the law of small numbers

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when S/sub n/=/spl Sigma//sub i=1//sup n/X/sub i/ is the sum of the (possibly dependent) binary random variables X/sub 1/,X/sub 2/,...,X/sub n/, with E(X/sub i/)=p/sub i/ and E(S/sub n/)=/spl lambda/, then D(P(S/sub n/)/spl par/Po(/spl lambda/)) /spl les//spl Sigma//sub i=1//sup n/p/sub i//sup 2/+[/spl Sigma//sub i=1//sup n/H(X/sub i/)-H(X/sub 1/,X/sub 2/,...,X/sub n/)] where D(P(S/sub n/)/spl par/Po(/spl lambda/)) is the relative entropy between the distribution of S/sub n/ and the Poisson (/spl lambda/) distribution. The first term in this bound measures the individual smallness of the X/sub i/ and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the X/sub i/ are independent, the following sharper bound is established: D(P(S/sub n/)/spl par/Po(/spl lambda/))/spl les/1//spl lambda/ /spl Sigma//sub i=1//sup n/ ((p/sub i//sup 3/)/(1-p/sub i/)) and it is also generalized to the case when the X/sub i/ are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.     

Reduced-state representations for trellis codes using constellation symmetry

This paper presents a symmetry-based technique for trellis-code state-diagram reduction that has more general applicability than the quasi-regularity technique of Rouanne et al. and Zehavi et al. for trellis codes using standard constellations and labelings. For a 2/sup /spl nu/x/-state trellis code, the new technique reduces the 2/sup 2/spl nu/x/ state diagram to 2/sup /spl nu/x+/spl nu/q/-state diagram where 0/spl les//spl nu//sub q//spl les//spl nu//sub x/. The particular value of /spl nu//sub q/ depends on the constellation labeling and the convolutional encoder. For standard rate-k/(k+1) set-partitioned trellis codes, /spl nu//sub q/=0, and the overall number of states is the same with the new technique as with quasi-regularity. For codes that are not quasi-regular (and thus not amenable to the quasi-regularity technique), the new technique often provides some improvement (when /spl nu//sub q/相似文献   

Near-ellipsoidal Voronoi coding

We consider a special case of Voronoi coding, where a lattice /spl Lambda/ in /spl Ropf//sup n/ is shaped (or truncated) using a lattice /spl Lambda/'={(m/sub 1/x/sub 1/,...,m/sub n/x/sub n/)|(x/sub 1/,...,x/sub n/)/spl isin//spl Lambda/} for a fixed m_=(m/sub 1/,...,m/sub n/)/spl isin/(/spl Nopf//spl bsol/{0,1})/sup n/. Using this technique, the shaping boundary is near-ellipsoidal. It is shown that the resulting codes can be indexed by standard Voronoi indexing algorithms plus a conditional modification step, as far as /spl Lambda/' is a sublattice of /spl Lambda/. We derive the underlying conditions on m_ and present generic near-ellipsoidal Voronoi indexing algorithms. Examples of constraints on m_ and conditional modification are provided for the lattices A/sub 2/, D/sub n/ (n/spl ges/2) and 2D/sub n//sup +/ (n even /spl ges/4).     

基于时间序列聚类的多雷达数据融合

针对多雷达数据融合问题，提出了基于时间序列的聚类算法，用于实现航迹相关，即以时间序列为基础把聚类模型转化为基于特征匹配的聚类算法。进一步考虑到多目标密集时，部分来自不同目标的数据可能比来自同一目标的数据更接近，易导致关联错误，为此提出了基于时间序列的模糊聚类算法。对上述两种算法的聚类结果，应用卡尔曼滤波器实现滤波跟踪，在不同的情况下仿真后发现，在跟踪目标较少且相互位置较远的情况下，两种算法均有效，在跟踪目标较多且相互位置靠近的情况下，基于时间序列的模糊聚类算法更有效。     

An orthonormal class of exact and simple DFT eigenvectors with a high degree of symmetry

The paper presents a novel orthonormal class of eigenvectors of the discrete Fourier transform (DFT) whose order N is factored as N=rM/sup 2/. The DFT eigenvectors have the form e=E/spl alpha/, where /spl alpha/ are eigenvectors of some /spl lscr/ /spl times//spl lscr/ matrices, given by, or related to, the DFT matrix of order r, with /spl lscr/ = r, 2r, or 4r, and the matrix E expands /spl alpha/ to the full DFT size N=rM/sup 2/. In particular, when N is an arbitrarily large power of 2, r may be 1 or 2. The resulting eigenvectors are expressed exactly with simple exponential expressions, have a considerable number of elements constrained to 0, and show a high degree of symmetry. The derivation of such a class is based on a partition of the N-dimensional linear space into subspaces of very small dimension (r, 2r or 4r).     

VLSI implementation of MIMO detection using the sphere decoding algorithm

Multiple-input multiple-output (MIMO) techniques are a key enabling technology for high-rate wireless communications. This paper discusses two ASIC implementations of MIMO sphere decoders. The first ASIC attains maximum-likelihood performance with an average throughput of 73 Mb/s at a signal-to-noise ratio (SNR) of 20 dB; the second ASIC shows only a negligible bit-error-rate degradation and achieves a throughput of 170 Mb/s at the same SNR. The three key contributing factors to high throughput and low complexity are: depth-first tree traversal with radius reduction, implemented in a one-node-per-cycle architecture, the use of the /spl lscr//sup /spl infin//-instead of /spl lscr//sup 2/-norm, and, finally, the efficient implementation of the enumeration approach recently proposed in . The resulting ASICs currently rank among the fastest reported MIMO detector implementations.     

Thinned coincident arrays for the direct measurement of the principal solution in radio astronomy

A new technique is described for the design of a thinned, linear, multiplicative array which directly measures the principal solution of a radio source distribution. The original filled multiplicative array with uniform element spacing /spl lscr/ is first generalized to an array of N/sub 1/+1 subarrays each with M/sub 1/+1 elements. A thinning factor of 1/2 is shown to be possible if M/sub 1/=N/sub 1/. Finally, if each subarray is further divided into smaller subarrays until the smallest are simply two element interferometers, then the principal solution can be directly measured but with far fewer elements. Significant thinning factors are achieved when the array is very large. The method can also be used to measure the principal solution with planar arrays, with very strong thinning occurring for large arrays.     

A gradient-based track-following controller optimization for hard disk drive

This paper presents a gradient-based parameter optimization method to find the optimal compensator that minimizes the standard deviation (/spl sigma//sub PES/) of the position error signal (PES) in a hard disk drive servo system. By using the plant response data and the PES gradient information based on the nominal plant model, optimal digital controllers that minimized the 3/spl sigma//sub PES/ of a plant with uncertainty were selected within a pre-found robust stable region. As a result, an optimal track-following controller that minimized the standard deviation of the measured PES (/spl sigma//sub PESm/) was able to be obtained without the prior knowledge of the disturbance and noise model. Furthermore, we proved that if the measurement noise is white, an optimal controller that minimizes the 3/spl sigma//sub PESm/ also minimizes the 3/spl sigma//sub PES/. Both simulation and implementation results suggest that such a gradient-based search process is faster than nongradient optimization methods such as random neighborhood search and genetic algorithms.     

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.     

On the /spl theta/-coverage and connectivity of large random networks

Wireless planar networks have been used to model wireless networks in a tradition that dates back to 1961 to the work of E. N. Gilbert. Indeed, the study of connected components in wireless networks was the motivation for his pioneering work that spawned the modern field of continuum percolation theory. Given that node locations in wireless networks are not known, random planar modeling can be used to provide preliminary assessments of important quantities such as range, number of neighbors, power consumption, and connectivity, and issues such as spatial reuse and capacity. In this paper, the problem of connectivity based on nearest neighbors is addressed. The exact threshold function for /spl theta/-coverage is found for wireless networks modeled as n points uniformly distributed in a unit square, with every node connecting to its /spl phi//sub n/ nearest neighbors. A network is called /spl theta/-covered if every node, except those near the boundary, can find one of its /spl phi//sub n/ nearest neighbors in any sector of angle /spl theta/. For all /spl theta//spl isin/(0,2/spl pi/), if /spl phi//sub n/=(1+/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, it is shown that the probability of /spl theta/-coverage goes to one as n goes to infinity, for any /spl delta/>0; on the other hand, if /spl phi//sub n/=(1-/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, the probability of /spl theta/-coverage goes to zero. This sharp characterization of /spl theta/-coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if /spl phi//sub n/=(1+/spl delta/)log/sub 2/n. Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed.     

Composite right/left-handed transmission line based compact resonant antennas for RF module integration

Several electrically small resonant antennas employing the composite right/left-handed transmission line (CRLH-TL) are presented for integration with portable RF modules. The proposed antenna designs are based on the unique property of anti-parallel phase and group velocity of the CRLH-TL at its fundamental mode. In this mode, the propagation constant increases as the frequency decreases, therefore, a small guided wavelength can be obtained at a lower frequency to provide the small /spl lambda//sub g//2 resonant length used to realize a compact antenna design. Furthermore, the physical size and the operational frequency of the antenna depend on the unit cell size and the equivalent transmission line model parameters of the CRLH-TL, including series inductance, series capacitance, shunt inductance and shunt capacitance. Optimization of these parameters as well as miniaturization techniques of the physical size of unit cell is investigated. A four unit-cell resonant antenna is designed and tested at 1.06 GHz. The length, width and height of the proposed antenna are 1/19/spl lambda//sub 0/, 1/23/spl lambda//sub 0/ and 1/83/spl lambda//sub 0/, respectively. In addition, a compact antenna using a 2-D three by three mushroom like unit cell arrangement is developed at 1.17 GHz, showing that an increased gain of 0.6 dB and higher radiation efficiency can be achieved over the first prototype antenna. The same design is applied in the development of a circularly polarized antenna operating at 2.46 GHz. A 116/spl deg/ beamwidth with axial ratio better than 3 dB is observed. The physical size of the proposed mushroom type small antenna and the circularly polarized antenna is 1/14/spl lambda//sub 0/ by 1/14/spl lambda//sub 0/ by 1/39/spl lambda//sub 0/ and 1/10/spl lambda//sub 0/ by 1/10/spl lambda//sub 0/ by 1/36/spl lambda//sub 0/, respectively.     

Analysis of Four-Frequency Nonlinear Reactance Circuits

Several advantages of multiple-frequency nonlinear reactance circuits are described in this paper. In particular, a circuit is considered in which a nonlinear reactance couples four basic frequencies: /spl omega//sub 0/, /spl omega//sub 1/,/spl omega//sub 2/, and /spl omega//sub 3/; these are so related that /spl omega//sub 2/ = /spl omega//sub 0/ + /spl omega//sub 1/ and /spl omega//sub 3/ = /spl omega//sub 0/ - /spl omega//sub 1/. Here, /spl omega//sub 0/ is taken to be the power source or pump. It is found to be desirable to allow for the possible presence of the pump harmonic, 2/spl omega//sub 0/, and individual cases are characterized by whether 2/spl omega//sub 0/, is present or not. The major results are as follows: 1) Unlimited amplification gain is theoretically possible at frequencies higher than the pump, by reflecting negative input resistance at /spl omega//sub 2/, but without relying on any effects due to pump harmonics. 2) Unlimited up- or down-conversion gains between /spl omega//sub 1/ and /spl omega//sub 2/ are theoretically possible in the additional presence of the first pump harmonic, but without reflecting negative input or output resistance. 3) Unlimited amplification gain is theoretically possible at frequencies both lower and higher than the pump fundamental, without reflecting negative input resistance.     

How to fool an unbounded adversary with a short key

The symmetric encryption problem which manifests itself when two parties must securely transmit a message m with a short shared secret key is considered in conjunction with a computationally unbounded adversary. As the adversary is unbounded, any encryption scheme must leak information about m; in particular, the mutual information between m and its ciphertext cannot be zero. Despite this, a family of encryption schemes is presented that guarantee that for any message space in {0,1}/sup n/ with minimum entropy n-/spl lscr/ and for any Boolean function h:{0,1}/sup n/ /spl rarr/ {0,1}, no adversary can predict h(m) from the ciphertext of m with more than 1/n/sup /spl omega/(1)/ advantage; this is achieved with keys of length /spl lscr/+/spl omega/(logn). In general, keys of length /spl lscr/+s yield a bound of 2/sup -/spl Theta/(s)/ on the advantage. These encryption schemes rely on no unproven assumptions and can be implemented efficiently. Applications of this to cryptosystems based on complexity-theoretic assumptions are discussed and, in addition, a simplified proof of a fundamental "elision lemma" of Goldwasser and Micali is provided.     

Order statistics from a logistic distribution and applications to survival and reliability analysis

Joint moments involving arbitrary powers of order statistics are the main concern. Consider order statistics u/sub 1/ /spl les/ u/sub 2/ /spl les/ /spl middot//spl middot//spl middot/ /spl les/ u/sub k/ coming from a simple random sample of size n from a real continuous population where u/sub 1/ = x/sub r(1):n/ is order-statistic #r/sub 1/, u/sub 2/ = x/sub r(1)+r(2):n/ is order statistic #(r/sub 1/ + r/sub 2/), et al., and u/sub k/ = x/sub r(1)+/spl middot//spl middot//spl middot/+r(k):n/ is order statistic #(r/sub 1/ +/spl middot//spl middot//spl middot/+ r/sub k/). Product moments are examined of the type E[u/sub 1//sup /spl alpha/(1)/ /spl middot/ u/sub 2//sup /spl alpha/(2)//sub /spl middot/ /spl middot//spl middot//spl middot//spl middot//u/sub k//sup /spl alpha/(k)/] where /spl alpha//sub 1/, ..., /spl alpha//sub k/ are arbitrary quantities that might be complex numbers, and E[/spl middot/] denotes the s-expected value. Some explicit evaluations are considered for a logistic population. Detailed evaluations of all integer moments of u/sub 1/ and recurrence relations, recurring only on the order of the moments, are given. Connections to survival functions in survival analysis, hazard functions in reliability situations, real type-1, type-2 /spl beta/ and Dirichlet distributions are also examined. Arbitrary product moments for the survival functions are evaluated. Very general results are obtained which can be used in many problems in various areas.