295 results
Search Results
2. Beta–Beta Bounds: Finite-Blocklength Analog of the Golden Formula.
- Author
-
Yang, Wei, Collins, Austin, Durisi, Giuseppe, Polyanskiy, Yury, and Poor, H. Vincent
- Subjects
MATHEMATICAL bounds ,CHANNEL coding ,NEYMAN-Pearson theorem ,RAYLEIGH fading channels ,STATISTICAL hypothesis testing - Abstract
It is well known that the mutual information between two random variables can be expressed as the difference of two relative entropies that depend on an auxiliary distribution, a relation sometimes referred to as the golden formula. This paper is concerned with a finite-blocklength extension of this relation. This extension consists of two elements: 1) a finite-blocklength channel-coding converse bound by Polyanskiy and Verdú, which involves the ratio of two Neyman–Pearson $\beta $ functions (beta–beta converse bound); and 2) a novel beta–beta channel-coding achievability bound, expressed again as the ratio of two Neyman–Pearson $\beta $ functions. To demonstrate the usefulness of this finite-blocklength extension of the golden formula, the beta–beta achievability and converse bounds are used to obtain a finite-blocklength extension of Verdú’s wideband-slope approximation. The proof parallels the derivation of the latter, with the beta–beta bounds used in place of the golden formula. The beta–beta (achievability) bound is also shown to be useful in cases where the capacity-achieving output distribution is not a product distribution due to, e.g., a cost constraint or structural constraints on the codebook, such as orthogonality or constant composition. As an example, the bound is used to characterize the channel dispersion of the additive exponential-noise channel and to obtain a finite-blocklength achievability bound (the tightest to date) for multiple-input multiple-output Rayleigh-fading channels with perfect channel state information at the receiver. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
3. A Single-Shot Approach to Lossy Source Coding Under Logarithmic Loss.
- Author
-
Shkel, Yanina Y. and Verdu, Sergio
- Subjects
CODING theory ,LOSSLESS data compression ,LOGARITHMS ,DECODING algorithms ,MATHEMATICAL bounds - Abstract
This paper considers the problem of lossy source coding with a specific distortion measure: logarithmic loss. The focus of this paper is on the single-shot approach, which exposes crisply the connection between lossless source coding with list decoding and lossy source coding with log-loss. Fixed-length and variable-length bounds are presented. Fixed-length bounds include the single-shot fundamental limit for average as well as excess distortion. Variable-length bounds include the single-shot fundamental limit for average as well as excess length. Two multi-terminal problems are addressed: coding with side information (Wyner–Ziv) and multiple descriptions coding. In both the cases, the application of the Shannon–McMillan theorem to the single-shot bounds yields the rate-distortion function and the rate distortion-region for stationary ergodic sources. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
4. The Capacity of Online (Causal) $q$ -Ary Error-Erasure Channels.
- Author
-
Chen, Zitan, Jaggi, Sidharth, and Langberg, Michael
- Subjects
CHANNEL capacity (Telecommunications) ,CODING theory ,ERROR correction (Information theory) ,MATHEMATICAL bounds ,ENCODING - Abstract
In the $q$ -ary online (or “causal”) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $\mathbf {x} =(x_{1},\ldots,x_{n}) \in \{0,1,\ldots,q-1\}^{n}$ symbol-by-symbol via a channel limited to at most $pn$ errors and $p^{*} n$ erasures. The channel is “online” in the sense that at the $i$ th step of communication the channel decides whether to corrupt the $i$ th symbol or not based on its view so far, i.e., its decision depends only on the transmitted symbols $(x_{1},\ldots,x_{i})$. This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge of the sent codeword $\mathbf {x}$. In this paper, we study the capacity of $q$ -ary online channels for a combined corruption model, in which the channel may impose at most $pn$ errors and at most $p^{*} n$ erasures on the transmitted codeword. The online channel (in both the error and erasure case) has seen a number of recent studies, which present both upper and lower bounds on its capacity. In this paper, we give a full characterization of the capacity as a function of $q,p$ , and $p^{*}$. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
5. Optimization-Based AMP for Phase Retrieval: The Impact of Initialization and $\ell_{2}$ Regularization.
- Author
-
Ma, Junjie, Maleki, Arian, and Xu, Ji
- Subjects
SIGNAL processing ,MATHEMATICAL optimization ,MATHEMATICAL regularization ,MATHEMATICAL bounds ,ITERATIVE methods (Mathematics) - Abstract
We consider an $\ell _{2}$ -regularized non-convex optimization problem for recovering signals from their noisy phaseless observations. We design and study the performance of a message passing algorithm that aims to solve this optimization problem. We consider the asymptotic setting $m,n \rightarrow \infty $ , $m/n \rightarrow \delta $ and obtain sharp performance bounds, where $m$ is the number of measurements and $n$ is the signal dimension. We show that for complex signals, the algorithm can perform accurate recovery with only $m = (({64}/{\pi ^{2}})-4)n \approx 2.5n$ measurements. Also, we provide a sharp analysis on the sensitivity of the algorithm to noise. We highlight the following facts about our message passing algorithm: 1) adding $\ell _{2}$ regularization to the non-convex loss function can be beneficial and 2) spectral initialization has a marginal impact on the performance of the algorithm. The sharp analyses, in this paper, not only enable us to compare the performance of our method with other phase recovery schemes but also shed light on designing better iterative algorithms for other non-convex optimization problems. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
6. Improved Upper Bound on the Network Function Computing Capacity.
- Author
-
Guang, Xuan, Yeung, Raymond W., Yang, Shenghao, and Li, Congduan
- Subjects
CAPACITY management (Computers) ,MATHEMATICAL bounds ,LINEAR network coding ,TOPOLOGY ,DECODERS & decoding ,INFORMATION theory - Abstract
The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. The edges in the network are assumed to be error-free and have limited capacity. The nodes in the network are assumed to have unbounded computing capability and be able to perform network coding. The computing rate of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. This improved upper bound not only is an enhancement of the previous upper bounds but also is the first tight upper bound on the computing capacity for computing an arithmetic sum over a certain non-tree network, which has been widely studied in the literature. We also introduce a multi-dimensional array approach that facilitates evaluation of the improved upper bound. Furthermore, we apply this bound to the problem of computing a vector-linear function over a network. With this bound, we are not only able to enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non-achievable, but whether it is asymptotically achievable or not remains open. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
7. Optimal Locally Repairable Codes Via Elliptic Curves.
- Author
-
Li, Xudong, Ma, Liming, and Xing, Chaoping
- Subjects
CIPHERS ,MATHEMATICAL bounds ,ORDERED algebraic structures ,ELLIPTIC curves ,MEASUREMENT of distances - Abstract
Constructing locally repairable codes achieving Singleton-type bound (we call them optimal codes in this paper) is a challenging task and has attracted great attention in the last few years. Tamo and Barg first gave a breakthrough result in this topic by cleverly considering subcodes of Reed-Solomon codes. Thus, $q$ -ary optimal locally repairable codes from subcodes of Reed-Solomon codes given by Tamo and Barg have length upper bounded by $q$. Recently, it was shown through extension of construction by Tamo and Barg that length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al.. Surprisingly it was shown by Barg et al. that, unlike classical MDS codes, $q$ -ary optimal locally repairable codes could have length bigger than $q+1$. Thus, it becomes an interesting and challenging problem to construct $q$ -ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we make use of rich algebraic structures of elliptic curves to construct a family of $q$ -ary optimal locally repairable codes of length up to $q+2\sqrt {q}$. It turns out that locality of our codes can be as big as 23 and distance can be linear in length. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
8. MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth.
- Author
-
Rawat, Ankit Singh, Tamo, Itzhak, Guruswami, Venkatesan, and Efremenko, Klim
- Subjects
CODING theory ,STORAGE area networks (Computer networks) ,MATHEMATICAL bounds ,DATA packeting ,BANDWIDTHS - Abstract
This paper addresses the problem of constructing maximum distance separable (MDS) codes that enable exact reconstruction (repair) of each code block by downloading a small amount of information from the remaining code blocks. The total amount of information flow from the remaining code blocks during this reconstruction process is referred to as repair bandwidth of the underlying code. Existing constructions of exact-repairable MDS codes with optimal repair bandwidth require working with large subpacketization levels, which restrict their applicability in practice. This paper presents two general approaches to construct exact-repairable MDS codes that aim at significantly reducing the required subpacketization level at the cost of slightly suboptimal repair bandwidth. The first approach provides MDS codes that have repair bandwidth at most twice the optimal repair bandwidth. In addition, these codes also have the smallest possible subpacketization level $O(r)$ , where $r$ denotes the number of parity blocks. This approach is then generalized to design codes that have their repair bandwidth approaching the optimal repair bandwidth at the cost of graceful increment in the required subpacketization level. The second approach transforms an MDS code with optimal repair bandwidth and large subpacketization level into a longer MDS code with small subpacketization level and near-optimal repair bandwidth. For a given $r$ , the codes constructed using this approach have their subpacketization level scaling logarithmically with the code length. In addition, the obtained codes require field size only linear in the code length and ensure load balancing among the intact code blocks in terms of the information downloaded from these blocks during the exact reconstruction of a code block. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
9. List Decoding for Arbitrarily Varying Multiple Access Channel Revisited: List Configuration and Symmetrizability.
- Author
-
Cai, Ning
- Subjects
MULTIPLE access protocols (Computer network protocols) ,MATHEMATICAL symmetry ,MATHEMATICAL bounds ,DECODING algorithms ,CHANNEL coding - Abstract
In a recent work, S. Nitinawarat obtained a lower bound and an upper bound for the minimum list size in list decoding for an arbitrarily varying multiple access channel (AVMAC), for which the interior of the capacity region of deterministic list codes is nonempty. In the same paper, he proved that for a binary AVMAC, the minimum list size is finite, if and only if the interior of the capacity region of random correlated codes is nonempty. The goal of this paper is to close the gap between the two bounds for the minimum list size. We find a necessary and sufficient condition for the list codes for an AVMAC to have a capacity region with a nonempty interior in terms of bipartite graphs. Therefore, we determine the minimum list size. Moreover, we prove that for any AVMAC, the minimum list size is finite, if and only if the interior of the capacity region of random correlated codes is nonempty. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
10. On the Rényi Divergence, Joint Range of Relative Entropies, and a Channel Coding Theorem.
- Author
-
Sason, Igal
- Subjects
DIVERGENCE theorem ,CHANNEL coding ,ENTROPY (Information theory) ,MATHEMATICAL optimization ,MATHEMATICAL bounds ,MAXIMUM likelihood statistics - Abstract
This paper starts by considering the minimization of the Rényi divergence subject to a constraint on the total variation distance. Based on the solution of this optimization problem, the exact locus of the points \bigl ( D(Q\|P1), D(Q\|P2) \bigr ) is determined when P1 , P2 , and $Q$ are arbitrary probability measures which are mutually absolutely continuous, and the total variation distance between P1 and P2 is not below a given value. It is further shown that all the points of this convex region are attained by probability measures which are defined on a binary alphabet. This characterization yields a geometric interpretation of the minimal Chernoff information subject to a constraint on the variational distance. This paper also derives an exponential upper bound on the performance of binary linear block codes (or code ensembles) under maximum-likelihood decoding. Its derivation relies on the Gallager bounding technique, and it reproduces the Shulman–Feder bound as a special case. The bound is expressed in terms of the Rényi divergence from the normalized distance spectrum of the code (or the average distance spectrum of the ensemble) to the binomially distributed distance spectrum of the capacity-achieving ensemble of random block codes. This exponential bound provides a quantitative measure of the degradation in performance of binary linear block codes (or code ensembles) as a function of the deviation of their distance spectra from the binomial distribution. An efficient use of this bound is considered. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
11. On the Diversity of Linear Transceivers in MIMO AF Relaying Systems.
- Author
-
Song, Changick and Ling, Cong
- Subjects
MIMO systems ,RADIO relay systems ,RADIO transmitter-receivers ,PERFORMANCE evaluation ,MATHEMATICAL bounds - Abstract
In this paper, we provide a comprehensive survey on designs and analyses of various relay-destination transceiving schemes, such as zero-forcing (ZF), minimum mean squared error (MMSE), and maximum information rate (MIR) criteria, in multiple-input multiple-output (MIMO) amplify-and-forward (AF) relaying systems. In the first part of the paper, we suggest a new framework for the transceiver designs utilizing a decomposable property of the error covariance matrix to give a general insight on the system and make the analysis more tractable. Then, in the second part of the paper, we provide an in-depth analysis on their diversity performance. Our analysis embraces two different scenarios, namely, the diversity-multiplexing tradeoff (DMT) and the diversity-rate tradeoff (DRT). First, we derive compact closed-form expressions for the DMT through tight upper and lower bounds. Then, we observe that while our DMT analysis accurately predicts performance of the ZF and MIR schemes, the MMSE-based designs exhibit a complicated rate-dependent behavior and, thus, are very unpredictable via DMT for finite rate cases. Thus, second, we highlight this interesting observation and characterize the diversity of the MMSE schemes at all finite rates. This leads to closed-form expressions for the DRT which reveals relationship between diversity, spectral efficiency, and the number of antennas at each node. The DRT analysis compliments our work on DMT, and thus, the paper provides a complete understanding on the diversity of MIMO AF relaying systems. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
12. Lower and Upper Bounds on the Density of Irreducible NFSRs.
- Author
-
Jiang, Yupeng and Lin, Dongdai
- Subjects
SHIFT registers ,MATHEMATICAL bounds ,BOOLEAN functions ,CIPHERS ,IRREDUCIBLE polynomials - Abstract
A nonlinear feedback shift register (NFSR) of $n$ -stage is called irreducible if, the family of output sequences of any NFSR of stage less than $n$ is not included in that of the NFSR. Tian and Qi in this paper [IEEE-IT, 2013(6),4006–4012] gave a lower bound on the density of irreducible NFSRs. In this paper, we improve their lower bound and also give an upper bound on the density of irreducible NFSRs. Moreover, the gap between our upper and lower bounds is less than 0.04. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
13. Extremality Between Symmetric Capacity and Gallager?s Reliability Function E0 for Ternary-Input Discrete Memoryless Channels.
- Author
-
Sakai, Yuta and Iwata, Ken-ichi
- Subjects
SYMMETRIC functions ,STATISTICAL reliability ,NONLINEAR theories ,MATHEMATICAL bounds - Abstract
This paper examines the exact ranges between the symmetric capacity and Gallager’s reliability function E0 for ternary-input discrete memoryless channels (T-DMCs) under a uniform input distribution. We first derive the two extremal ternary-input strongly symmetric channels taking the maximum and minimum values of the E0 function among all ternary-input strongly symmetric channels with a fixed capacity. Extending the results of ternary-input strongly symmetric channels, we second derive the exact ranges between capacity and the E0 function for ternary-input Gallager-symmetric channels. We third show that the exact ranges between the symmetric capacity and the E0 function of T-DMCs coincide with the ranges of ternary-input Gallager-symmetric channels. In particular, we identify the extremal channels taking the maximum and minimum of E0 among all T-DMCs with a fixed symmetric capacity. As applications of the results, we describe some bounds of error exponents for T-DMCs with a fixed symmetric capacity. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
14. On Codes Achieving Zero Error Capacities in Limited Magnitude Error Channels.
- Author
-
Bose, Bella, Elarief, Noha, and Tallini, Luca G.
- Subjects
ERROR probability ,CODING theory ,DECODING algorithms ,ERROR analysis in mathematics ,MATHEMATICAL bounds - Abstract
Shannon in his 1956 seminal paper introduced the concept of the zero error capacity, C0 , of a noisy channel. This is defined as the least upper bound of rates, at which, it is possible to transmit information with zero probability of error. At present not many codes are known to achieve the zero error capacity. In this paper, some codes which achieve zero error capacities in limited magnitude error channels are described. The code lengths of these zero error capacity achieving codes can be of any finite length $n=1,2,\ldots$ , in contrast to the long lengths required for the known regular capacity achieving codes, such as turbo codes, LDPC codes, and polar codes. Both wrap around and non-wrap around limited magnitude error models are considered in this paper. For non-wrap around error model, the exact value of zero error capacities is derived, and optimal non-systematic and systematic codes are designed. The non-systematic codes achieve the zero error capacity with any finite length. The optimal systematic codes achieve the systematic zero error capacity of the channel, which is defined as the zero error capacity with the additional requirements that the communication must be carried out with a systematic code. It is also shown that the rates of the proposed systematic codes are equal to or approximately equal to the zero error capacity of the channel. For the wrap around model bounds are derived for the zero error capacity and in many cases the bounds give the exact value. In addition, optimal wrap around non-systematic and systematic codes are developed which either achieve or are close to achieving the zero error capacity with finite length. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
15. Linear Programming Bounds for Entanglement-Assisted Quantum Error-Correcting Codes by Split Weight Enumerators.
- Author
-
Lai, Ching-Yi and Ashikhmin, Alexei
- Subjects
LINEAR programming ,CODING theory ,QUANTUM states ,MATHEMATICAL bounds ,HAMMING codes - Abstract
Linear programming approaches have been applied to derive upper bounds on the size of classical and quantum codes. In this paper, we derive similar results for general quantum codes with entanglement assistance by considering a type of split weight enumerator. After deriving the MacWilliams identities for these enumerators, we are able to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. Our Singleton bound and Hamming bound are more general than the previous bounds for entanglement-assisted quantum stabilizer codes. In addition, we show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large. On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve the linear programming bounds on the minimum distance of quantum codes of small length. In particular, we show that there is no $[[27, 15, 5]]$ or $[[28, 14, 6]]$ stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement quantum stabilizer codes with length up to 20 are significantly improved. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
16. Codes Between MBR and MSR Points With Exact Repair Property.
- Author
-
Ernvall, Toni
- Subjects
INFORMATION storage & retrieval systems ,CODING theory ,MATHEMATICAL bounds ,PARAMETERS (Statistics) ,METHODOLOGY - Abstract
In this paper, distributed storage systems with exact repair are studied. Constructions for exact-regenerating codes between the minimum storage regenerating (MSR) and the minimum bandwidth regenerating (MBR) points are given. To the best of our knowledge, no previous construction of exact-regenerating codes between MBR and MSR points is done except in the works by Tian et al. and Sasidharan et al. In contrast to their works, the methods used here are elementary. In this paper, it is shown that in the case that the parameters \(n\) , \(k\) , and \(d\) are close to each other, the given construction is close to optimal when comparing with the known functional repair capacity. This is done by showing that when the distances of the parameters \(n\) , \(k\) , and \(d\) are fixed but the actual values approach to infinity, the fraction of the performance of constructed codes with exact repair and the known capacity of codes with functional repair, approaches to one. Also, a simple variation of the constructed codes with almost the same performance is given. Also some bounds for the capacity of exact-repairing codes are given. These bounds illustrate the relationships between storage codes with different parameters. [ABSTRACT FROM PUBLISHER]
- Published
- 2014
- Full Text
- View/download PDF
17. Security in Locally Repairable Storage.
- Author
-
Agarwal, Abhishek and Mazumdar, Arya
- Subjects
INFORMATION storage & retrieval systems ,INFORMATION technology security ,CONFIDENTIAL communications ,ACCESS to information ,MATHEMATICAL bounds - Abstract
In this paper we extend the notion of locally repairable codes to secret sharing schemes. The main problem that we consider is to find optimal ways to distribute the shares of a secret among a set of storage-nodes (participants) such that the content of each node (share) can be recovered by using the contents of only few other nodes, and at the same time the secret can be reconstructed by only some allowable subsets of nodes. As a special case, an eavesdropper observing some set of specific nodes (such as less than certain number of nodes) does not get any information. In other words, we propose to study a locally repairable distributed storage system that is secure against a passive eavesdropper that can observe some subsets of nodes. We provide a number of results related to such systems, including upper bounds and achievability results on the number of bits that can be securely stored with these constraints. In particular, we provide conditions under which a locally repairable code can be turned into a secret sharing scheme and extend the results of secure repairable storage to cooperative repair and storage on networks. In addition, we consider perfect secret sharing schemes over general access structures under locality constraints and give an example of a perfect secret sharing scheme that can have small locality. Finally, we provide a lower bound on the size of a share compared with the size of the secret that shows how locality affects the sizes of shares in a perfect scheme. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
18. Empirical Lipschitz Constants for the Renyi Entropy Maximum Likelihood Estimator.
- Author
-
Konstantinides, John M. and Andreadis, Ioannis
- Subjects
RENYI'S entropy ,MAXIMUM likelihood statistics ,MATHEMATICAL bounds ,MATHEMATICAL optimization ,INFORMATION theory - Abstract
Mathematical tools that are widely employed for the distribution-free analysis of the finite-sample performance of empirical estimators—like Efron-Stein’s inequality, or Azuma’s martingale inequality and derivatives—rely on the provision of tight bounds for the Lipschitz constants of the estimators. Lipschitz constants can be easily derived for simple functionals of the empirical measures, such as the Shannon or the Tsallis entropy. However, obtaining tight bounds for more generalized entropy functionals which cannot be decomposed into sums of identical terms is much more involved. The goal in this paper is the derivation of (empirical) Lipschitz constants for the maximum likelihood estimator of the family of Renyi entropies of order $\lambda >0$ , $\lambda \neq 1$. Analytic solutions for the optimal constants are obtained for the most important special cases; namely, for $0 < \lambda < 1$ , for $1 < \lambda < 2$ as well as for $\lambda =2$ (collision entropy) and $\lambda = 3$. For the remaining cases where no analytic solution is obtained (i.e., $\lambda > 2$ , $\lambda \neq 3$), an efficient way to compute the optimal constants is derived by reducing the complexity of the underlying optimization problem from exponential ${\varOmega}(n^{\| \mathcal {A} \|-1})$ to linear $\mathcal {O}(n)$ , where $n$ the number of available samples and $\| \mathcal {A} \| \geq 2$ the number of symbols of the source (with the assumption $\| \mathcal {A} \|$ does not grow with $n$). The optimal constants are subsequently used for the distribution-free performance analysis of the maximum likelihood estimator of Renyi entropy; this includes variance and concentration bounds, both under the assumption of independence as well as under strong mixing conditions. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
19. Expurgated Bounds for the Asymmetric Broadcast Channel.
- Author
-
Averbuch, Ran, Weinberger, Nir, and Merhav, Neri
- Subjects
BROADCAST channels ,MATHEMATICAL bounds ,MAXIMUM likelihood decoding ,ENTROPY (Information theory) ,ERROR probability - Abstract
This paper contains two main contributions concerning the expurgation of hierarchical ensembles for the asymmetric broadcast channel. The first is an analysis of the optimal maximum likelihood (ML) decoders for the weak and strong user. Two different methods of code expurgation will be used, that will provide two competing error exponents. The second is the derivation of expurgated exponents under the generalized stochastic likelihood decoder (GLD). We prove that the expurgated exponents achieved for the hierarchical ensemble under GLD decoding are at least as good as the maximum between the random coding error exponents derived in an earlier work by Averbuch and Merhav (2018) and one of our ML–based expurgated exponents. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
20. On a Fractional Version of Haemers’ Bound.
- Author
-
Bukh, Boris and Cox, Christopher
- Subjects
COMPUTER storage capacity ,MATHEMATICAL bounds ,CHANNEL coding ,GRAPH theory ,LINEAR programming ,HAFNIUM - Abstract
In this paper, we present a fractional version of Haemers’ bound on the Shannon capacity of a graph, which is originally due to Blasiak. This bound is a common strengthening of both Haemers’ bound and the fractional chromatic number of a graph. We show that this fractional version outperforms any bound on the Shannon capacity that could be attained through Haemers’ bound. We show also that this bound is multiplicative, unlike Haemers’ bound. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
21. A Lower Bound on the Probability of Error of Polar Codes over BMS Channels.
- Author
-
Shuval, Boaz and Tal, Ido
- Subjects
CODING theory ,PROBABILITY theory ,MATHEMATICAL bounds ,ENTROPY (Information theory) ,CHANNEL coding ,DECODE & forward communication - Abstract
Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
22. Generalization and Improvement of the Levenshtein Lower Bound for Aperiodic Correlation.
- Author
-
Arlery, Fabien, Tan, UyHour, and Rabaste, Olivier
- Subjects
MATHEMATICAL bounds ,NUMERICAL analysis ,ALGORITHMS ,X-ray diffraction ,STATISTICAL correlation - Abstract
This paper deals with lower bounds on aperiodic correlation of sequences. It intends to solve two open questions. The first one is on the validity of the Levenshtein bound for a set of sequences other than binary sequences or those over the roots of unity. Although this result could be a priori extended to polyphase sequences, a formal demonstration is presented here, proving that it does actually hold for these sequences. The second open question is on the possibility to find a bound tighter than Welch’s, in the case of a set consisting of two sequences $M = 2$. By including the specific structure of correlation sequences, a tighter lower bound is introduced for this case. Besides, this method also provides in the cases $M = 3$ and $M = 4$ a tighter bound than the up-to-now tightest bound provided by Liu et al. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
23. Distortion Bounds for Source Broadcast Problems.
- Author
-
Yu, Lei, Li, Houqiang, and Li, Weiping
- Subjects
ELECTRIC distortion ,MATHEMATICAL bounds ,MEMORYLESS systems ,CODING theory ,GAUSSIAN processes - Abstract
This paper investigates the joint source-channel coding problem of sending a memoryless source over a memoryless broadcast channel. An inner bound and several outer bounds on the admissible distortion region are derived, which, respectively, generalize and unify several existing bounds. As a consequence, we also obtain an inner bound and an outer bound for the degraded broadcast channel case. When specialized to the Gaussian or binary source broadcast, the inner bound and outer bound not only recover the best known inner bound and outer bound in the literature but also generate some new results. Besides, we also extend the inner bound and outer bounds to the Wyner–Ziv source broadcast problem, i.e., source broadcast with side information available at decoders. Some new bounds are obtained when specialized to the Wyner–Ziv Gaussian and Wyner–Ziv binary cases. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
24. Bounds on the Size of Locally Recoverable Codes.
- Author
-
Cadambe, Viveck R. and Mazumdar, Arya
- Subjects
MATHEMATICAL bounds ,BINARY codes ,INFORMATION retrieval ,CONCATENATED codes ,DOWNLOADING ,CODING theory ,CLOUD computing - Abstract
In a locally recoverable or repairable code, any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure (erasure). A common objective is to repair the node by downloading data from as few other storage nodes as possible. In this paper, we bound the minimum distance of a code in terms of its length, size, and locality. Unlike the previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence, the Simplex codes are the first example of an optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
25. Finite-Length Analysis of Spatially-Coupled Regular LDPC Ensembles on Burst-Erasure Channels.
- Author
-
Aref, Vahid, Schmalen, Laurent, and Rengaswamy, Narayanan
- Subjects
BINARY erasure channels (Telecommunications) ,MEMORYLESS systems ,PARITY-check matrix ,ITERATIVE decoding ,MONTE Carlo method ,MATHEMATICAL bounds - Abstract
Regular spatially-coupled low-density parity-check ensembles have gained significant interest, since they were shown to universally achieve the capacity of binary memoryless channels under low-complexity belief-propagation decoding. In this paper, we focus primarily on the performance of these ensembles over binary channels affected by bursts of erasures. We first develop an analysis of the finite length performance for a single burst per code word and no errors otherwise. We first assume that the burst erases a complete spatial position, modeling for instance node failures in distributed storage. We provide new tight lower bounds for the block erasure probability ( P_ \mathrm \scriptscriptstyle B ) at finite block length and bounds on the coupling parameter for being asymptotically able to recover the burst. We further show that expurgating the ensemble can improve the block erasure probability by several orders of magnitude. Later we extend our methodology to more general channel models. In a first extension, we consider bursts that can start at a random location in the code word and span across multiple spatial positions. Besides the finite length analysis, we determine by means of density evolution the maximum correctable burst length. In a second extension, we consider the case where in addition to a single burst, random bit erasures may occur. Finally, we consider a block erasure channel model which erases each spatial position independently with some probability $p$ , potentially introducing multiple bursts simultaneously. All results are verified using Monte-Carlo simulations. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
26. Minimax Lower Bounds on Dictionary Learning for Tensor Data.
- Author
-
Shakeri, Zahra, Bajwa, Waheed U., and Sarwate, Anand D.
- Subjects
RANDOM noise theory ,MATHEMATICAL bounds ,MACHINE learning ,CALCULUS of tensors ,DATA structures ,MATRIX decomposition - Abstract
This paper provides fundamental limits on the sample complexity of estimating dictionaries for tensor data. The specific focus of this work is on $K$ th-order tensor data and the case where the underlying dictionary can be expressed in terms of $K$ smaller dictionaries. It is assumed the data are generated by linear combinations of these structured dictionary atoms and observed through white Gaussian noise. This work first provides a general lower bound on the minimax risk of dictionary learning for such tensor data and then adapts the proof techniques for specialized results in the case of sparse and sparse-Gaussian linear combinations. The results suggest the sample complexity of dictionary learning for tensor data can be significantly lower than that for unstructured data: for unstructured data it scales linearly with the product of the dictionary dimensions, whereas for tensor-structured data the bound scales linearly with the sum of the product of the dimensions of the (smaller) component dictionaries. A partial converse is provided for the case of 2nd-order tensor data to show that the bounds in this paper can be tight. This involves developing an algorithm for learning highly-structured dictionaries from noisy tensor data. Finally, numerical experiments highlight the advantages associated with explicitly accounting for tensor data structure during dictionary learning. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
27. Classification of Bent Monomials, Constructions of Bent Multinomials and Upper Bounds on the Nonlinearity of Vectorial Functions.
- Author
-
Xu, Yuwei, Carlet, Claude, Mesnager, Sihem, and Wu, Chuankun
- Subjects
NONLINEAR theories ,MATHEMATICAL bounds ,VECTOR algebra ,CODING theory - Abstract
This paper is composed of two main parts related to the nonlinearity of vectorial functions. The first part is devoted to maximally nonlinear (n,m) functions (the so-called bent vectorial functions), which contribute to an optimal resistance to both linear and differential attacks on symmetric cryptosystems. They can be used in block ciphers at the cost of additional diffusion/compression/expansion layers, or as building blocks for the construction of substitution boxes (S-boxes), and they are also useful for constructing robust codes and algebraic manipulation detection codes. A main issue on bent vectorial functions is to characterize bent monomial functions Tr_{m}^{n} (\lambda x^{d}) from \mathbb {F}_{2^{n}} to \mathbb F2^{m} (where m is a divisor of n ) leading to a classification of those bent monomials. We also treat the case of functions with multiple trace terms involving general results and explicit constructions. Furthermore, we investigate some open problems raised by Pasalic et al. and Muratović-Ribić et al. in a series of papers on vectorial functions. The second part is devoted to the nonlinearity of (n,m) -functions. No tight upper bound is known when \frac n2
- Published
- 2018
- Full Text
- View/download PDF
28. A Tight Upper Bound on the Second-Order Coding Rate of the Parallel Gaussian Channel With Feedback.
- Author
-
Fong, Silas L. and Tan, Vincent Y. F.
- Subjects
ASYMPTOTIC expansions ,GAUSSIAN channels ,DECODERS & decoding ,RANDOM variables ,MATHEMATICAL bounds ,MATHEMATICAL models - Abstract
This paper investigates the asymptotic expansion for the maximum rate of fixed-length codes over a parallel Gaussian channel with feedback under the following setting: a peak power constraint is imposed on every transmitted codeword, and the average error probabilities of decoding the transmitted message are non-vanishing as the blocklength increases. The main contribution of this paper is a self-contained proof of an upper bound on the first- and second-order asymptotics of the parallel Gaussian channel with feedback. The proof techniques involve developing an information spectrum bound followed by using Curtiss’ theorem to show that a sum of dependent random variables associated with the information spectrum bound converges in distribution to a sum of independent random variables, thus facilitating the use of the usual central limit theorem. Combined with existing achievability results, our result implies that the presence of feedback does not improve the first- and second-order asymptotics. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
29. Replication-Based Outer Bounds: On the Optimality of “Half the Cake” for Rank-Deficient MIMO Interference Networks.
- Author
-
Yuan, Bofeng, Sun, Hua, and Jafar, Syed Ali
- Subjects
MIMO systems ,DEGREES of freedom ,ANTENNAS (Electronics) ,GAUSSIAN processes ,MATHEMATICAL bounds ,MATHEMATICAL models - Abstract
In order to gain new insights into multiple-input–multiple-output (MIMO) interference networks, the optimality of \sum k=1^{K} Mk/2 (half the cake per user) degrees of freedom is explored for a K -user MIMO interference channel where the cross-channels have arbitrary rank constraints, and the k th transmitter and receiver are equipped with Mk antennas each. The result consolidates and significantly generalizes results from prior studies by Krishnamurthy et al., of rank-deficient interference channels where all users have M antennas; and by Tang et al., of full rank interference channels where the $k$ th user pair has M_{k} antennas. The broader outcome of this paper is a novel class of replication-based outer bounds for arbitrary rank-constrained MIMO interference networks where replicas of existing users are added as auxiliary users and the network connectivity is chosen to ensure that any achievable scheme for the original network also works in the new network. The replicated network creates a new perspective of the problem, so that even simple arguments such as user cooperation become quite powerful when applied in the replicated network, giving rise to stronger outer bounds, than when applied directly in the original network. Remarkably, the replication-based bounds are broadly applicable not only to MIMO interference channels with arbitrary rank-constraints, but much more broadly, even beyond Gaussian settings. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
30. New Constructions of Asymptotically Optimal Codebooks With Multiplicative Characters.
- Author
-
Heng, Ziling, Ding, Cunsheng, and Yue, Qin
- Subjects
CODE division multiple access ,CHARACTERS of groups ,FINITE fields ,MATHEMATICAL bounds ,ALGEBRAIC coding theory ,ALGEBRAIC codes ,MATHEMATICAL models - Abstract
In practical applications, such as direct spread code division multiple access communications, space-time codes and compressed sensing, and codebooks with small inner-product correlation are required. It is extremely difficult to construct codebooks achieving the Levenshtein bound. In this paper, two new constructions of infinitely many codebooks with multiplicative characters of finite fields are presented. These constructions produce complex codebooks asymptotically achieving the Levenshtein bound and codebooks asymptotically achieving the Welch bound. The codebooks presented in this paper have new parameters. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
31. Cramér–Rao Lower Bounds of RSS-Based Localization With Anchor Position Uncertainty.
- Author
-
Angjelichinoski, Marko, Denkovski, Daniel, Atanasovski, Vladimir, and Gavrilovska, Liljana
- Subjects
MATHEMATICAL bounds ,ALGORITHMS ,MATHEMATICAL inequalities ,TOPOLOGY ,FISHER information - Abstract
The location awareness is useful in many wireless networking solutions, such as cellular, ad hoc, self-organizing, cognitive radio networks, and so on. The RSS-based, non-Bayesian source localization is of particular interest, due to the presence of the RSS measurements in all radio devices, as well as the instantaneous estimations without extensive training and learning phases. However, most RSS-based localization algorithms usually neglect problems arising from inherent network topology uncertainty. The positions of some measuring anchors, usually assumed to be precisely known in advance, are often a subject of previous estimation, which propagates errors in the source localization procedure and results in performance degradation. A joint localization framework, termed source position estimation for anchor position uncertainty reduction (SPEAR), has been recently proposed as a possible solution to the problem of RSS-based localization in the presence of network topology uncertainty. The framework simultaneously estimates the positions of the sources and the uncertain anchors and serves as robust tool that provides improved source localization performance and more reliable anchor position estimates. This paper focuses on the theoretical assessment of SPEAR’s performance by deriving its fundamental lower bounds using the Cramér–Rao information inequality. The main contribution of this paper is the detailed information-theoretic interpretation of the obtained results. The interpretation provides valuable insight into the essence of the SPEAR localization problem because it identifies different position information components in the observed data, discovers how they are mutually related, and determines how they contribute toward the resulting position information. This paper also provides geometric interpretation of the obtained results and illustrates the principles of distribution of position information in space. The theoretical results as well as their information-theoretic and geometric interpretations can be used as a benchmark for RSS-based location-aware systems that operate in the presence of network topology uncertainty. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
32. Rate-Distortion Bounds for Wyner–Ziv Coding With Gaussian Scale Mixture Correlation Noise.
- Author
-
Bassi, Francesca, Fraysse, Aurelia, Dupraz, Elsa, and Kieffer, Michel
- Subjects
RATE distortion theory ,GAUSSIAN mixture models ,RANDOM noise theory ,MATHEMATICAL bounds ,MEMORYLESS systems ,DECODERS (Electronics) - Abstract
The objective of this paper is the characterization of the Wyner–Ziv rate-distortion function for memoryless continuous sources, when the correlation between the sources is modeled via an additive noise channel. Modeling the distribution of the correlation noise via a Gaussian mixture, with discrete or continuous mixing variable, provides a unified signal model able to describe a wide class of distributions, useful in the context of practical applications. The Wyner–Ziv rate-distortion function associated with this signal model cannot, in general, be obtained in analytical form. This paper contributes a method for its analysis, by providing computable upper and lower bounds. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
33. Duality Codes and the Integrality Gap Bound for Index Coding.
- Author
-
Yu, Hao and Neely, Michael J.
- Subjects
CODING theory ,MATHEMATICAL bounds ,DATA packeting ,LINEAR programming ,ALGORITHMS - Abstract
This paper considers a base station that delivers packets to multiple receivers through a sequence of coded transmissions. All receivers overhear the same transmissions. Each receiver may already have some of the packets as side information, and requests another subset of the packets. This problem is known as the index coding problem and can be represented by a bipartite digraph. An integer linear program is developed that provides a lower bound on the minimum number of transmissions required for any coding algorithm. Conversely, its linear programming relaxation is shown to provide an upper bound that is achievable by a simple form of vector linear coding. Thus, the information theoretic optimum is bounded by the integrality gap between the integer program and its linear relaxation. In the special case, when the digraph has a planar structure, the integrality gap is shown to be zero, so that exact optimality is achieved. Finally, for nonplanar problems, an enhanced integer program is constructed that provides a smaller integrality gap. The dual of this problem corresponds to a more sophisticated partial clique coding strategy that time-shares between maximum distance separable codes. This paper illuminates the relationship between index coding, duality, and integrality gaps between integer programs and their linear relaxations. [ABSTRACT FROM PUBLISHER]
- Published
- 2014
- Full Text
- View/download PDF
34. Comments On “Information-Theoretic Key Agreement of Multiple Terminals—Part I”.
- Author
-
Gohari, Amin and Anantharam, Venkat
- Subjects
KEY agreement protocols (Computer network protocols) ,INFORMATION theory ,MATHEMATICAL bounds ,PROBABILITY theory ,MARKOV processes - Abstract
Theorem 5 of A. Gohari, V. Anantharam, IEEE Transactions on Information Theory, vol. 56, no. 8, pp. 3973-3996, 2010, states an upper bound on the secrecy capacity for the source model problem. It has a three page proof given in Appendix B of the paper. Unfortunately, we show that this bound does not provide any improvement over the simpler bound given in Corollary 1 of the paper. We also provide an example of a family of two agent source model problems where the one-way secrecy rate in each direction is zero, but the secrecy rate is nonzero and can be determined exactly as a conditional mutual information. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
35. Worst-case Redundancy of Optimal Binary AIFV Codes and Their Extended Codes.
- Author
-
Hu, Weihua, Yamamoto, Hirosuke, and Honda, Junya
- Subjects
BINARY codes ,MATHEMATICAL bounds ,ENTROPY (Information theory) ,HUFFMAN codes ,DATA compression - Abstract
Binary almost instantaneous fixed-to-variable length (AIFV) codes are lossless codes that generalize the class of instantaneous fixed-to-variable length codes. The code uses two code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, which is the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to coincide with the worst-case redundancy of the codes. Along with this, the worst-case redundancy is derived for sources with p\max \geq 1 /2, where p\max is the probability of the most likely source symbol. In addition, we propose an extension of binary AIFV codes, which use $m$ code trees and allow at most $m$ -bit decoding delay. We show that the worst-case redundancy of the extended binary AIFV codes is $1/m$ for $m \leq 4$ . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
36. \mathbb Z2\mathbb Z2[u] ?Cyclic and Constacyclic Codes.
- Author
-
Aydogdu, Ismail, Abualrub, Taher, and Siap, Irfan
- Subjects
CYCLIC codes ,LINEAR codes ,ORDERED algebraic structures ,MODULES (Algebra) ,MATHEMATICAL bounds - Abstract
Following the very recent studies on \mathbb Z2\mathbb Z4 -additive codes, \mathbb Z2\mathbb Z2[u] -linear codes have been introduced by Aydogdu et al. In this paper, we introduce and study the algebraic structure of cyclic, constacyclic codes and their duals over the R -module \mathbb {Z}_{2}^\alpha R^\beta where R=\mathbb {Z}_{2}+u\mathbb {Z}_{2}=\left \{{0,1,u,u+1}\right \} is the ring with four elements and u^2=0 . We determine the generating independent sets and the types and sizes of both such codes and their duals. Finally, we present a bound and an optimal family of codes attaining this bound and also give some illustrative examples of binary codes that have good parameters which are obtained from the cyclic codes in \mathbb Z_2^\alpha R^\beta . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
37. Meta-Fibonacci Codes:Efficient Universal Coding of Natural Numbers.
- Author
-
Avila, Bruno T. and Campello De Souza, Ricardo M.
- Subjects
NATURAL numbers ,FIBONACCI sequence ,NUMBER systems ,MATHEMATICAL bounds ,DATA compression - Abstract
In this paper, we address the problem of the universal coding of natural numbers. A new numeration system is introduced, which is based on variable- $r$ meta-Fibonacci sequences and it is a generalization of the Zeckendorf numeration system. This new numeration system is used to construct binary, prefix-free, uniquely decodable universal codes called meta-Fibonacci codes. The main advantage of these codes is that they are parametrized by a sequence of numbers, the sequence o. By controlling the growth of the values of this sequence, we can control the length of the code word. This means that we can provide a general framework for building efficient universal coders for natural numbers. Such framework is applied to the upper bounds of the code word length defined by Leung-Yan-Cheong and Cover (1978), Levenshtein (1968), and Ahlswede (1997). There is no other code meeting these bounds. In each case, we build meta-Fibonacci codes and demonstrate that the upper bound of their code word length is satisfied up to an additive constant, thereby solving these open problems. The framework may be applied to other upper bounds that satisfy Kraft inequality. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
38. Sensing Tensors With Gaussian Filters.
- Author
-
Chretien, Stephane and Wei, Tianwen
- Subjects
COMPRESSED sensing ,GAUSSIAN mixture models ,INDEPENDENT component analysis ,HIDDEN Markov models ,TENSOR algebra ,MATHEMATICAL bounds - Abstract
Sparse recovery from linear Gaussian measurements has been the subject of much investigation since the breaktrough papers Candès et al. and Donoho on compressed sensing. Application to sparse vectors and sparse matrices via least squares penalized with sparsity promoting norms is now well understood thanks to tools, such as Gaussian mean width, statistical dimension, and the notion of descent cones. Extention of these ideas to low rank tensor recovery is starting to enjoy considerable interest due to its many potential applications to independent component analysis, hidden Markov models, Gaussian mixture models, and hyperspectral image analysis, to name a few. In this paper, we demonstrate that the recent approach of Vershynin provides useful error bounds in the tensor setting with the nuclear norm or the Romera-Paredes–Pontil penalization. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
39. Optimal Rebuilding of Multiple Erasures in MDS Codes.
- Author
-
Wang, Zhiying, Tamo, Itzhak, and Bruck, Jehoshua
- Subjects
ERROR-correcting codes ,DECODERS & decoding ,BANDWIDTHS ,HAMMING distance ,MATHEMATICAL bounds ,COMPUTER algorithms - Abstract
Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with $r$ redundancy nodes can correct any $r$ node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, $e$ erasures are a more likely failure event, for some $1 \le e < r$ . Hence, a natural question is how much information do we need to access in order to rebuild $e$ storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of $e$ erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of $1/r$ for the rebuilding of any systematic node when $e=1$ ; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any $r$ erasures can be corrected by accessing some of the remaining information, and any $e=1$ erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of $e/r$ for systematic nodes of MDS codes, for any $1 \le e \le r$ ; 2) we construct systematic codes that achieve optimal rebuilding ratio of $1/r$ , for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
40. Volume of Metric Balls in High-Dimensional Complex Grassmann Manifolds.
- Author
-
Pitaval, Renaud-Alexandre, Wei, Lu, Tirkkonen, Olav, and Corander, Jukka
- Subjects
RATE distortion theory ,MATHEMATICAL bounds ,CODING theory ,GRASSMANN manifolds ,HYPERPLANES ,SUBSPACES (Mathematics) - Abstract
Volume of metric balls relates to rate-distortion theory and packing bounds on codes. In this paper, the volume of balls in complex Grassmann manifolds is evaluated for an arbitrary radius. The ball is defined as a set of hyperplanes of a fixed dimension with reference to a center of possibly different dimensions, and a generalized chordal distance for unequal dimensional subspaces is used. First, the volume is reduced to a 1-D integral representation. The overall problem boils down to evaluating a determinant of a matrix of the same size as the subspace dimensionality. Interpreting this determinant as a characteristic function of the Jacobi ensemble, an asymptotic analysis is carried out. The obtained asymptotic volume is moreover refined using moment-matching techniques to provide a tighter approximation in finite-size regimes. Finally, the pertinence of the derived results is shown by rate-distortion analysis of source coding on Grassmann manifolds. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
41. On the Minimal Overcompleteness Allowing Universal Sparse Representation.
- Author
-
Mulayoff, Rotem and Michaeli, Tomer
- Subjects
SPARSE approximations ,SIGNAL processing ,BETA distribution ,GEOMETRY ,MATHEMATICAL bounds - Abstract
Sparse representation over redundant dictionaries constitute a good model for many classes of signals (e.g., patches of natural images, segments of speech signals, and so on). However, despite its popularity, a very little are known about the representation capacity of this model. In this paper, we study how redundant a dictionary must be so as to allow any vector to admit a sparse approximation with a prescribed sparsity and a prescribed level of accuracy. We address this problem, both in a worst-case setting and in an average-case one. For each scenario, we derive lower and upper bounds on the minimal required overcompleteness. Our bounds have simple closed-form expressions that allow to easily deduce the asymptotic behavior in large dimensions. In particular, we find that the required overcompleteness grows exponentially with the sparsity level and polynomially with the allowed representation error. This implies that universal sparse representation is practical only at moderate sparsity levels, but can be achieved with a relatively high accuracy. As a side effect of our analysis, we obtain a tight lower bound on the regularized incomplete beta function, which may be interesting in its own right. We illustrate the validity of our results through numerical simulations, which support our findings. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
42. Lattice Gaussian Sampling by Markov Chain Monte Carlo: Bounded Distance Decoding and Trapdoor Sampling.
- Author
-
Wang, Zheng and Ling, Cong
- Subjects
DECODERS & decoding ,GAUSSIAN distribution ,MARKOV chain Monte Carlo ,MATHEMATICAL bounds ,MIMO systems - Abstract
Sampling from the lattice Gaussian distribution plays an important role in various research fields. In this paper, the Markov chain Monte Carlo (MCMC)-based sampling technique is advanced in several fronts. First, the spectral gap for the independent Metropolis-Hastings-Klein (MHK) algorithm is derived, which is then extended to Peikert’s algorithm and rejection sampling; we show that independent MHK exhibits faster convergence. Then, the performance of bounded distance decoding (BDD) using MCMC is analyzed, revealing a flexible trade-off between the decoding radius and complexity. MCMC is further applied to trapdoor sampling, again offering a trade-off between security and complexity. Finally, the independent multiple-try Metropolis-Klein (MTMK) algorithm is proposed to enhance the convergence rate. The proposed algorithms allow parallel implementation, which is beneficial for practical applications. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
43. Quasi-Cyclic Protograph-Based Raptor-Like LDPC Codes for Short Block-Lengths.
- Author
-
Ranganathan, Sudarsan V. S., Divsalar, Dariush, and Wesel, Richard D.
- Subjects
LOW density parity check codes ,CHANNEL coding ,ITERATIVE decoding ,ERROR rates ,MATHEMATICAL bounds - Abstract
Protograph-based Raptor-like low-density parity-check codes (PBRL codes) are a family of easily encodable rate-compatible low-density parity-check (LDPC) codes. PBRL codes have an excellent performance across all design rates. Quasi-cyclic (QC) PBRL code families permit high-speed decoder implementations. PBRL codes designed thus far, for both long and short block-lengths, have been based on optimizing the iterative decoding threshold of the protograph of the PBRL family at various design rates. This paper introduces a design method to obtain better QC PBRL code families at short block-lengths (of a few hundred bits) for low frame error rate (FER) requirements. We first select a protomatrix for the highest design rate. To add a new row to lower the rate, we keep all the previously obtained rows of the PBRL protomatrix fixed and select the new row that maximizes an upper bound on the minimum distance of any QC-LDPC code that can be obtained from the protomatrix. The new QC PBRL code families outperform the original PBRL codes at short block-lengths by providing a significantly better low-FER performance. The standard approach to computing the aforementioned upper bounds requires complexity that grows exponentially with the size of the protomatrix. However, we show that the structure of the PBRL protomatrix lets us obtain the upper bounds with complexity that grows only linearly with the size of the PBRL protomatrix. Using the complexity reduction results, we also establish an equivalence between the exhaustive search to design a new row for the PBRL protomatrix according to the new design method and an integer linear program. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
44. Separable Codes for the Symmetric Multiple-Access Channel.
- Author
-
D'yachkov, Arkadii, Polyanskii, Nikita, Vorobyev, Ilya, and Shchukin, Vladislav
- Subjects
MULTIPLE access protocols (Computer network protocols) ,DECODERS & decoding ,RANDOM codes (Coding theory) ,BOOLEAN matrices ,MATHEMATICAL bounds - Abstract
A binary matrix is called an ${s}$ -separable code for the disjunctive multiple-access channel (disj-MAC) if Boolean sums of sets of ${s}$ columns are all distinct. The well-known issue of the combinatorial coding theory is to obtain upper and lower bounds on the rate of ${s}$ -separable codes for the ${disj}$ -MAC. In our paper, we generalize the problem and discuss upper and lower bounds on the rate of ${q}$ -ary ${s}$ -separable codes for the models of noiseless symmetric MAC, i.e., at each time instant the output signal of MAC is a symmetric function of its ${s}$ input signals. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
45. Noisy Adaptive Group Testing: Bounds and Algorithms.
- Author
-
Scarlett, Jonathan
- Subjects
GROUP testing ,NOISE measurement ,MATHEMATICAL bounds ,ALGORITHMS ,INFORMATION theory - Abstract
The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly noisy tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and many more. One of the defining features of the group testing problem is the distinction between the non-adaptive and adaptive settings. In the non-adaptive case, all tests must be designed in advance, whereas in the adaptive case, each test can be designed based on the previous outcomes. While tight information-theoretic limits and near-optimal practical algorithms are known for the adaptive setting in the absence of noise, surprisingly little is known in the noisy adaptive setting. In this paper, we address this gap by providing information-theoretic achievability and converse bounds under various noise models, as well as a slightly weaker achievability bound for a computationally efficient variant. These bounds are shown to be tight or near-tight in a broad range of scaling regimes, particularly at low noise levels. The algorithms used for the achievability results have the notable feature of only using two or three stages of adaptivity. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
46. From Cages to Trapping Sets and Codewords: A Technique to Derive Tight Upper Bounds on the Minimum Size of Trapping Sets and Minimum Distance of LDPC Codes.
- Author
-
Dehghan, Ali and Banihashemi, Amir H.
- Subjects
LOW density parity check codes ,CODING theory ,ERROR correction (Information theory) ,MATHEMATICAL bounds ,TANNER graphs - Abstract
Cages, defined as regular graphs with minimum number of nodes for a given girth, are well-studied in graph theory. Trapping sets are graphical structures responsible for error floor of low-density parity-check (LDPC) codes, and are well investigated in coding theory. In this paper, we make connections between cages and trapping sets. In particular, starting from a cage (or a modified cage), we construct a trapping set in multiple steps. Based on the connection between cages and trapping sets, we then use the available results in graph theory on cages and derive tight upper bounds on the size of the smallest trapping sets for variable-regular LDPC codes with a given variable degree and girth. The derived upper bounds in many cases meet the best known lower bounds and thus provide the actual size of the smallest trapping sets. Considering that non-zero codewords are a special case of trapping sets, we also derive tight upper bounds on the minimum weight of such codewords, i.e., the minimum distance, of variable-regular LDPC codes as a function of variable degree and girth. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
47. On the Finite Length Scaling of $q$ -Ary Polar Codes.
- Author
-
Goldin, Dina and Burshtein, David
- Subjects
CODING theory ,POLYNOMIALS ,DISCRETE memoryless channels ,MATHEMATICAL bounds ,BROADCAST channels - Abstract
The polarization process of polar codes over a prime $q$ -ary alphabet is studied. Recently, it has been shown that the blocklength of polar codes with prime alphabet size scales polynomially with respect to the inverse of the gap between code rate and channel capacity. However, except for the binary case, the degree of the polynomial in the bound is extremely large. In this paper, a different approach to computing the degree of this polynomial for any prime alphabet size is shown. This approach yields a lower degree polynomial for various values of the alphabet size that were examined. It is also shown that even lower degree polynomial can be computed with an additional numerical effort. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
48. Median-Truncated Nonconvex Approach for Phase Retrieval With Outliers.
- Author
-
Zhang, Huishuai, Chi, Yuejie, and Liang, Yingbin
- Subjects
SIGNAL processing ,NONCONVEX programming ,MACHINE learning ,MATHEMATICAL bounds ,GAUSSIAN channels - Abstract
This paper investigates the phase retrieval problem, which aims to recover a signal from the magnitudes of its linear measurements. We develop statistically and computationally efficient algorithms for the situation when the measurements are corrupted by sparse outliers that can take arbitrary values. We propose a novel approach to robustify the gradient descent algorithm by using the sample median as a guide for pruning spurious samples in initialization and local search. Adopting a Poisson loss and a reshaped quadratic loss, respectively, we obtain two algorithms termed median-truncated Wirtinger flow and median-reshaped Wirtinger flow, both of which provably recover the signal from a near-optimal number of measurements when the measurement vectors are composed of independent and identically distributed Gaussian entries, up to a logarithmic factor, even when a constant fraction of the measurements is adversarially corrupted. We further show that both algorithms are stable in the presence of additional dense bounded noise. Our analysis is accomplished by developing non-trivial concentration results of median-related quantities, which may be of independent interest. We provide numerical experiments to demonstrate the effectiveness of our approach. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
49. A Unified Random Coding Bound.
- Author
-
Lee, Si-Hyeon and Chung, Sae-Young
- Subjects
RANDOM codes (Coding theory) ,UNIFIED modeling language ,DUALITY theory (Mathematics) ,GAUSSIAN processes ,MATHEMATICAL bounds - Abstract
In this paper, we prove a unified achievability bound that generalizes and improves random coding bounds for any combination of source coding, channel coding, joint source–channel coding, and coding for computing problems assuming blockwise node operation. As a general network setup, we consider an acyclic discrete memoryless network, where the network demands and constraints are specified by a joint-typicality constraint on the whole channel input and output sequences. For achievability, a basic building block for node operation consists of simultaneous nonunique decoding, simultaneous compression, and symbol-by-symbol mapping. Our bound can be useful for deriving random coding bounds without error analysis, especially for large and complex networks. In particular, our bound can be used for unifying and generalizing many known relaying strategies. For example, a generalized decode-compress-amplify-and-forward bound is obtained as a simple corollary of our main theorem, and it is shown to strictly outperform the previously known relaying schemes. Furthermore, by exploiting the symmetry in our bound, we formally define and characterize three types of network duality based on channel input–output reversal and network flow reversal combined with packing–covering duality. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
50. Bounds on the Reliability Function of Typewriter Channels.
- Author
-
Dalai, Marco and Polyanskiy, Yury
- Subjects
MATHEMATICAL bounds ,ALGEBRAIC geometry ,PENTAGONS ,LINEAR programming ,HAMMING codes - Abstract
New lower and upper bounds on the reliability function of typewriter channels are given. Our lower bounds improve upon the (multiletter) expurgated bound of Gallager, furnishing a new and simple counterexample to a conjecture made in 1967 by Shannon, Gallager and Berlekamp on its tightness. The only other known counter example is due to Katsman, Tsfasman and Vlăduţ who used algebraic-geometric codes on a $q$ -ary symmetric channels, $q\geq 49$. Here we prove, by introducing dependence between codewords of a random ensemble, that the conjecture is false even for a typewriter channel with $q=4$ inputs. In the process, we also demonstrate that Lovász’s proof of the capacity of the pentagon was implicitly contained (but unnoticed!) in the works of Jelinek and Gallager on the expurgated bound done at least ten years before Lovász. In the opposite direction, new upper bounds on the reliability function are derived for channels with an odd number of inputs by using an adaptation of Delsarte’s linear programming bound. First, we derive a bound based on the minimum distance, which combines Lovász’s construction for bounding the graph capacity with the McEliece-Rodemich-Rumsey-Welch construction for bounding the minimum distance of codes in the Hamming space. Then, for the particular case of cross-over probability 1/2, we derive an improved bound by also using the method of Kalai and Linial to study the spectrum distribution of codes. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.