waashk/dblp huggingface dataset:
a coding algorithm for constant weight vectors: a geometric approach based on dissections. we present a novel technique for encoding and decoding constant weight binary vectors that uses a geometric interpretation of the codebook. our technique is based on embedding the codebook in a euclidean space of dimension equal to the weight of the code. the encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this euclidean space. an inductive dissection algorithm is developed for constructing such a bijection. we prove that the algorithm is correct and then analyze its complexity. the complexity depends on the weight of the vector, rather than on the block length as in other algorithms. this approach is advantageous when the weight is smaller than the square root of the block length.
a collaborative training algorithm for distributed learning. in this paper, an algorithm is developed for collaboratively training networks of kernel-linear least-squares regression estimators. the algorithm is shown to distributively solve a relaxation of the classical centralized least-squares regression problem. a statistical analysis shows that the generalization error afforded agents by the collaborative training algorithm can be bounded in terms of the relationship between the network topology and the representational capacity of the relevant reproducing kernel hilbert space. numerical experiments suggest that the algorithm is effective at reducing noise. the algorithm is relevant to the problem of distributed learning in wireless sensor networks by virtue of its exploitation of local communication. several new questions for statistical learning theory are proposed.
golden space-time block-coded modulation. in this paper, block-coded modulation is used to design a 2×2 multiple-input multiple-output (mimo) space-time code for slow fading channels. the golden code is chosen as the inner code; the scheme is based on a set partitioning of the golden code using two-sided ideals whose norm is a power of two. in this case, a lower bound for the minimum determinant is given by the minimum hamming distance. the description of the ring structure of the quotients suggests further optimization in order to improve the overall distribution of determinants. simulation results show that the proposed schemes achieve a significant gain over the uncoded golden code.
diversity product properties of lu-kumar's space-time codes. in this paper, we show that the diversity products of the full transmit diversity space-time block codes proposed by lu-kumar (we call them lu-kumar's codes) with quadratic-amplitude modulation (qam) constellations are lower bounded by 4. we present a sufficient condition on the minimum hamming weight of the linear binary full-rank space-time code such that this lower bound is met. we show that the special lu-kumar codes does satisfy the sufficient condition, and therefore, the diversity products of the special lu-kumar codes are 4, where "special" means that the linear binary full-rank space-time codes are general but specially constructed by lu-kumar.
capacity bounds for the gaussian interference channel. the capacity region of the two-user gaussian interference channel (ic) is studied. three classes of channels are considered: weak, one-sided, and mixed gaussian ics. for the weak gaussian ic, a new outer bound on the capacity region is obtained that outperforms previously known outer bounds. the sum capacity for a certain range of channel parameters is derived. for this range, it is proved that using gaussian codebooks and treating interference as noise are optimal. it is shown that when gaussian codebooks are used, the full han-kobayashi achievable rate region can be obtained by using the naive han-kobayashi achievable scheme over three frequency bands (equivalently, three subspaces). for the one-sided gaussian ic, an alternative proof for the sato's outer bound is presented. we derive the full han-kobayashi achievable rate region when gaussian codebooks are utilized. for the mixed gaussian ic, a new outer bound is obtained that outperforms previously known outer bounds. for this case, the sum capacity for the entire range of channel parameters is derived. it is proved that the full han-kobayashi achievable rate region using gaussian codebooks is equivalent to that of the one-sided gaussian ic for a particular range of channel parameters.
robust precoder adaptation for mimo links with noisy limited feedback. in this paper, we propose two robust limited feedback designs for multiple-input multiple-output (mimo) adaptation. the first scheme, namely, the combined design jointly optimizes the adaptation, csit (channel state information at the transmitter) feedback as well as index assignment strategies. the second scheme, namely, the decoupled design, focuses on the index assignment problem given an error-free limited feedback design. simulation results show that the proposed framework has significant capacity gain compared to the naive design (designed assuming there is no feedback error). furthermore, for large number of feedback bits cfb, we show that under two-nearest constellation feedback channel assumption, the mimo capacity loss (due to noisy feedback) of the proposed robust design scales like o(pe2-cfb/t+1 for some positive integer t. hence, the penalty due to noisy limited feedback in the proposed robust design approaches zero as cfb increases.
sampling theorems for signals from the union of finite-dimensional linear subspaces. compressed sensing is an emerging signal acquisition technique that enables signals to be sampled well belowthe nyquist rate, given that the signal has a sparse representation in an orthonormal basis. in fact, sparsity in an orthonormal basis is only one possible signal model that allows for sampling strategies below the nyquist rate. in this paper, we consider a more general signal model and assume signals that live on or close to the union of linear subspaces of lowdimension.we present sampling theorems for this model that are in the same spirit as the nyquist-shannon sampling theorem in that they connect the number of required samples to certain model parameters. contrary to the nyquist-shannon sampling theorem, which gives a necessary and sufficient condition for the number of required samples as well as a simple linear algorithm for signal reconstruction, the model studied here is more complex. we therefore concentrate on two aspects of the signal model, the existence of one to one maps to lower dimensional observation spaces and the smoothness of the inverse map. we show that almost all linear maps are one to one when the observation space is at least of the same dimension as the largest dimension of the convex hull of the union of any two subspaces in the model. however, we also show that in order for the inverse map to have certain smoothness properties such as a given finite lipschitz constant, the required observation dimension necessarily depends logarithmically on the number of subspaces in the signal model. in other words, while unique linear sampling schemes require a small number of samples depending only on the dimension of the subspaces involved, in order to have stable sampling methods, the number of samples depends necessarily logarithmically on the number of subspaces in the model. these results are then applied to two examples, the standard compressed sensing signal model in which the signal has a sparse representation in an orthonormal basis and to a sparse signal model with additional tree structure.
some designs and normalized diversity product upper bounds for lattice-based diagonal and full-rate space-time block codes. in this paper, we first present two tight upper bounds for the normalized diversity products (or product distances) of 2 × 2 diagonal space-time block codes from quadratic extensions on q(i) and q(ζ6), where i = √-1 and ζ6 = exp(i2π/6). two such codes are shown to reach the tight upper bounds and therefore have the maximal normalized diversity products. we present two new diagonal space-time block codes from higher order algebraic extensions on q(i) and q(ζ6) for three and four transmit antennas. we also present a nontight upper bound for normalized diversity products of 2 × 2 diagonal space-time block codes with qam information symbols, i.e., in z [i], from general 2 × 2 complex-valued generating matrices. we then present an n × n-diagonal space-time code design method directly from 2n real integers based on extended complex lattices (of generating matrix size n × 2n) that are shown to have better normalized diversity products than the optimal diagonal cyclotomic codes do. we finally use the optimal 2 × 2 diagonal space-time codes from the optimal quadratic extensions to construct two 2 × 2 full-rate space-time block codes and find that both of them have better normalized diversity products than the golden code does.
noncoherent mimo communication: grassmannian constellations and efficient detection. this paper considers the design of both a transmitter and a receiver for noncoherent communication over a frequency-flat, richly scattered multiple-input multiple-output (mimo) channel. the design is guided by the fact that at high signal-to-noise ratios (snrs), the ergodic capacity of the channel can be achieved by input signals that are isotropically distributed on the (compact) grassmann manifold. the first part of the paper considers the design of grassmannian constellations that mimic the isotropic distribution. a subspace perturbation analysis is used to determine an appropriate metric for the distance between grassmannian constellation points, and using this metric, greedy, direct and rotation-based techniques for designing constellations are proposed. these techniques offer different tradeoffs between the minimum distance of the constellation and the design complexity. in addition, the rotation-based technique results in constellations that have lower storage requirements and admit a natural "quasi-set-partitioning" binary labeling. in the second part of the paper, a reduced search suboptimum detector is proposed. the development of this detector relies on the subspace perturbation analysis and exploits the geometric properties of the grassmann manifold and the isotropic distribution of the constellation points and the noise realizations. the performance of this detector is comparable to that of the maximum likelihood detector, but it requires considerably less computational effort. finally, in order to assess the performance of a given constellation, an exact expression is provided for the pairwise error probability of the ml detector. in comparison to existing pairwise error probability expressions, the proposed expression is numerically stable and does not require the evaluation of residues at poles with high multiplicities.
efficient and generalized pairing computation on abelian varieties. in this paper, we propose a new method for constructing a bilinear pairing over (hyper)elliptic curves, which we call the r-ate pairing. this pairing is a generalization of the ate and atei pairing, and can be computed more efficiently. using the r-ate pairing, the loop length in miller's algorithm can be as small as log(r1/φ(k)) for some pairing-friendly elliptic curves which have not reached this lower bound. therefore, we obtain savings of between 29% and 69% in overall costs compared to the atei pairing. on supersingular hyperelliptic curves of genus 2, we show that this approach makes the loop length in miller's algorithm shorter than that of the ate pairing.
asymptotic analysis of outage region in cdma mimo systems. uplink code-division multiple access (cdma) multiple-input and multiple-output (mimo) systems are considered in the large system limit within the assumptions of synchrony and frequency flat fading. the outage region maximizing the sum capacity of non-outage users is obtained, which extends the criterion of outage in single-input and single-output (siso) cdma systems.
further results on stable recovery of sparse overcomplete representations in the presence of noise. sparse overcomplete representations have attracted much interest recently for their applications to signal processing. in a recent work, donoho, elad, and temlyakov (2006) showed that, assuming sufficient sparsity of the ideal underlying signal and approximate orthogonality of the overcomplete dictionary, the sparsest representation can be found, at least approximately if not exactly, by either an orthogonal greedy algorithm or by l1-norm minimization subject to a noise tolerance constraint. in this paper, we sharpen the approximation bounds under more relaxed conditions. we also derive analogous results for a stepwise projection algorithm.
compressed and privacy-sensitive sparse regression. recent research has studied the role of sparsity in high-dimensional regression and signal reconstruction, establishing theoretical limits for recovering sparse models. this line of work shows that l1-regularized least squares regression can accurately estimate a sparse linear model from noisy examples in high dimensions. we study a variant of this problem where the original n input variables are compressed by a random linear transformation to m ≪ n examples in p dimensions, and establish conditions under which a sparse linear model can be successfully recovered from the compressed data. a primary motivation for this compression procedure is to anonymize the data and preserve privacy by revealing little information about the original data. we characterize the number of projections that are required for l1-regularized compressed regression to identify the nonzero coefficients in the true model with probability approaching one, a property called "sparsistence." we also show that l1-regularized compressed regression asymptotically predicts as well as an oracle linear model, a property called "persistence." finally, we characterize the privacy properties of the compression procedure, establishing upper bounds on the mutual information between the compressed and uncompressed data that decay to zero.
error-pattern-correcting cyclic codes tailored to a prescribed set of error cluster patterns. a new class of cyclic codes is discussed which is highly tailored to a prescribed set of dominant error cluster patterns. the cyclic code construction is based on a generator polynomial that produces a distinct syndrome set for each error pattern in the target set. by tailoring the generator polynomial specifically to the set of dominant error patterns, the code becomes highly effective in handling single and multiple occurrences of dominant error patterns at a very high code rate. a list decoding strategy based on a set of test word-error events is developed for the proposed codes, which efficiently utilizes both the algebraic information from the captured syndrome and the reliability measures provided by the local correlators matched to the dominant error patterns. by forcing a decoder to correct a single-pattern event for each test input word, multiple decoders running in parallel on the list of test words can effectively correct multiple error-pattern occurrences within the channel detector output word.
tracking stopping times through noisy observations. a novel quickest detection setting is proposed, generalizing the well-known bayesian change-point detection model. suppose {(xi,yi)}i≥1 is a sequence of pairs of random variables, and that s is a stopping time with respect to {xi}i≥1. the problem is to find a stopping time t with respect to {yi}i≥1 that optimally tracks s, in the sense that t minimizes the expected reaction delay e(t-s)+, while keeping the false-alarm probability p(t < s) below a given threshold α ∈ [0,1]. this problem formulation applies in several areas, such as in communication, detection, forecasting, and quality control. our results relate to the situation where the xi's and yi's take values in finite alphabets and where s is bounded by some positive integer κ. by using elementary methods based on the analysis of the tree structure of stopping times, we exhibit an algorithm that computes the optimal average reaction delays for all α ∈ [0,1], and constructs the associated optimal stopping times t. under certain conditions on {(xi,yi)}i≥1 and s, the algorithm running time is polynomial in κ.
shortening array codes and the perfect 1-factorization conjecture. the existence of a perfect 1-factorization of the complete graph with n nodes, namely, kn, for arbitrary even number n, is a 40-year-old open problem in graph theory. so far, two infinite families of perfect 1-factorizations have been shown to exist, namely, the factorizations of kp+1 and k2p, where p is an arbitrary prime number (p < 2). it was shown in previous work that finding a perfect 1-factorization of kn is related to a problem in coding, specifically, it can be reduced to constructing an mds (minimum distance separable), lowest density array code. in this paper, a new method for shortening arbitrary array codes is introduced. it is then used to derive the kp+1 family of perfect 1-factorization from the k2p family. namely, techniques from coding theory are used to prove a new result in graph theory--that the two factorization families are related.
self-organization properties of csma/ca systems and their consequences on fairness. decentralized medium access control schemes for wireless networks based on csma/ca, such as the ieee 802.11 protocol, are known to be unfair. in multihop networks, they can even favor some links to such an extent that the others suffer from virtually complete starvation. this observation has been reported in quite a few works, but the factors causing it are still not well understood. we find that the capture effect and the relative values of the receive and carrier sensing ranges play a crucial role in the performance of these protocols. using a simple markovian model, we show that an idealized csma/ca protocol suffers from starvation when the receiving and sensing ranges are equal, but quite surprisingly that this unfairness is reduced or even disappears when these two ranges are sufficiently different. we also show that starvation has a positive counterpart, namely organization. when its access intensity is large the protocol organizes the transmissions in space in such a way that it maximizes the number of concurrent successful transmissions. we obtain exact formulæ for the so-called spatial reuse of the protocol on large line networks.
combinatorial constructions for optimal two-dimensional optical orthogonal codes. optical orthogonal codes (oocs) have been designed for ocdma. a one-dimensional (1-d) optical orthogonal code (1-d ooc) is a set of one-dimensional binary sequences having good auto and cross-correlations. one limitation of 1-d ooc is that the length of the sequence increases rapidly when the number of users or the weight of the code is increased, which means large bandwidth expansion is required if a big number of codewords is needed. to lessen this problem, two-dimensional (2-d) coding (also called multiwavelength oocs) was invested. a two dimensional (2-d) optical orthogonal code (2-d ooc) is a set of u × v matrices with (0, 1) elements having good auto and cross-correlations. recently, many researchers are working on constructions and designs of 2-d oocs. in this paper, we shall reveal the combinatorial properties of 2-d oocs and give an equivalent combinatorial description of a 2-d ooc. based on this, we are able to use combinatorial methods to obtain many optimal 2-d oocs.
vector gaussian multiple description with two levels of receivers. the problem of l multiple descriptions of a stationary and ergodic gaussian source with two levels of receivers is investigated. each of the first-level receivers receive (an arbitrary subset) k of the l descriptions, (k < l). the second-level receiver receives all l descriptions. all the receivers, both at the first level and the second level, reconstruct the source using the subset of descriptions they receive. the corresponding reconstructions are subject to quadratic distortion constraints. our main result is the derivation of an outer bound on the sum rate of the descriptions so that the distortion constraints are met. we show that an analog-digital separation architecture involving joint gaussian vector quantizers and a binning scheme meets this outer bound with equality for several scenarios. these scenarios include the case when the distortion constraints are symmetric and the case for general distortion constraints with k = 2 and l = 3.
classification of unique mappings for 8psk based on bit-wise distance spectra. the performance of bit-interleaved coded modulation (bicm) with (or without) iterative decoding (id) is significantly influenced by the mapping of bits to the symbol constellation. our main objective in this paper is to develop a systematic design approach for bicm-id schemes, ensuring the best possible performance with iterative decoding. although useful mappings for bicm-id have been found based on various search strategies, no attempt has been made to systematically enumerate and classify all unique mappers for a given constellation. as the basis for a systematic enumeration and classification, we define the average bit-wise distance spectrum for a mapping from bits to symbols. different bit-wise distance spectra are derived assuming no prior information or full prior information, respectively. the bitwise distance spectra determine corresponding bit-wise error probability and bit-wise mutual information. the latter allows us to use the classification of mappings with unique bit-wise distance spectra to also classify mappings with unique extremal points in the corresponding extrinsic information transfer (exit) curves. as an example of our approach, we classify 8psk mappings into 86 classes of unique mappings according to bit-wise distance spectra. the classification can be used to significantly reduce the complexity of the search for suitable mappers for bicm-id. for 8psk and a given encoder, only 86 different mappings need to be investigated. as examples of the systematic design approach, the best 8psk mappings for minimizing the convergence threshold are found for concatenation with the rate 1/2 (5, 7)8 and (133,171)8 convolutional codes, and the rate 1/2 umts turbo code with identical constituent convolutional codes (15/13)8.
lower limits of discrete universal denoising. in the spirit of results on universal compression, we compare the performance of universal denoisers on discrete memoryless channels to that of the best performance obtained by an omniscient kth-order sliding-window denoiser, namely, one that is tuned to the transmitted noiseless sequence. we show that the additional loss incurred in the worst case by any universal denoiser on a length-n sequence grows at least like ω(ck/√n), where c is a constant depending on the channel parameters and the loss function. this shows that for fixed k the additional loss incurred by the discrete universal denoiser (dude) is no larger than a constant multiplicative factor of the best possible. furthermore, we compare universal denoisers to denoisers that are aware of the distribution of the transmitted noiseless sequence. we show that, even for this weaker target loss, for any universal denoiser there exists some distribution for the noiseless sequence corresponding to a sequence of independent and identically distributed (i.i.d.) random variables whose optimum expected loss is lower than that incurred by the universal denoiser by ω(1/√n).