The Experts below are selected from a list of 5208 Experts worldwide ranked by ideXlab platform

Thinh Nguyen - One of the best experts on this subject based on the ideXlab platform.

  • on bounds and closed form expressions for capacities of Discrete Memoryless Channels with invertible positive matrices
    IEEE Transactions on Vehicular Technology, 2020
    Co-Authors: Thuan Nguyen, Thinh Nguyen
    Abstract:

    While capacities of Discrete Memoryless Channels are well studied, it is still not possible to obtain a closed-form expression for the capacity of an arbitrary Discrete Memoryless Channel (DMC). In this paper, we study a class of DMCs whose Channel matrix is an invertible positive matrix. This class of Channel matrices can be used to model many real-world settings. Next, an elementary technique based on Karush-Kuhn-Tucker (KKT) conditions is used to obtain (1) a good upper bound of a Discrete Memoryless Channel having an invertible positive Channel matrix and (2) a closed-form expression for the capacity if the Channel matrix satisfies certain conditions related to its singular value and its Gershgorin's disk.

  • on bounds and closed form expressions for capacities of Discrete Memoryless Channels with invertible positive matrices
    arXiv: Information Theory, 2020
    Co-Authors: Thuan Nguyen, Thinh Nguyen
    Abstract:

    While capacities of Discrete Memoryless Channels are well studied, it is still not possible to obtain a closed-form expression for the capacity of an arbitrary Discrete Memoryless Channel. This paper describes an elementary technique based on Karush Kuhn Tucker (KKT) conditions to obtain (1) a good upper bound of a Discrete Memoryless Channel having an invertible positive Channel matrix and (2) a closed-form expression for the capacity if the Channel matrix satisfies certain conditions related to its singular value and its Gershgorin disk.

  • on closed form capacities of Discrete Memoryless Channels
    Vehicular Technology Conference, 2018
    Co-Authors: Thuan Nguyen, Thinh Nguyen
    Abstract:

    While capacities of Discrete Memoryless Channels are well studied, it is still not possible to obtain a closed form expression of the capacity for an arbitrary Discrete Memoryless Channel. This paper shows an elementary technique based on Karush-Kuhn-Tucker (KKT) conditions to obtain a closed form expression for a good upper bound of an arbitrary Discrete Memoryless Channel. Furthermore, using this technique, we are able to obtain the closed form expressions for the capacities of Channels whose Channel matrices satisfy a number of conditions.

Hideki Yagi - One of the best experts on this subject based on the ideXlab platform.

  • variable length Channel resolvability for Discrete Memoryless sources and Channels
    International Symposium on Information Theory, 2018
    Co-Authors: Hideki Yagi, Te Sun Han
    Abstract:

    The problem of Channel resolvability, where a given output probability distribution over a Channel is approximated by encoding uniform random number as a Channel input, is addressed. The Channel resolvability has recently been generalized to the variable-length setting, where the variable-length uniform random number instead of the fixed-length one is encoded. Though the optimum resolvability rate can be reduced compared with the fixed-length resolvability, it is not yet clear how much resolvability rate can be saved even when the given source and Channel are stationary and Memoryless. Given a stationary Memoryless source and a Discrete Memoryless Channel, this paper establishes a single-letter formula for the variable-length resolvability under the variational distance as an approximation measure. When the Channel is a full-rank Discrete Memoryless Channel, the established formula reduces to a further simpler formula characterized by the mutual information between the source and the Channel. The established formula also recovers a known formula for the variable-length source resolvability.

  • finding the capacity of a quantized binary input dmc
    International Symposium on Information Theory, 2012
    Co-Authors: Brian M. Kurkoski, Hideki Yagi
    Abstract:

    Consider a binary-input, M-output Discrete Memoryless Channel (DMC) where the outputs are quantized to K levels, with K < M. The subject of this paper is the maximization of mutual information between the input and quantizer output, over both the input distribution and Channel quantizer. This can be regarded as finding the capacity of a quantized DMC. An algorithm is given, which either finds the optimal input distribution and corresponding quantizer, or declares a failure.

  • Channel quantizers that maximize random coding exponents for binary input Memoryless Channels
    International Conference on Communications, 2012
    Co-Authors: Hideki Yagi, Brian M. Kurkoski
    Abstract:

    The problem of finding the optimum output quantizer for a given Discrete Memoryless Channel is investigated, where the quantizer output has fewer values than the Channel output. While mutual information has received attention as an objective function for optimization, the focus of this paper is use of the random coding exponent, which was originally derived by Gallager, as criteria. Two problems are addressed, where one problem is a partial problem of the other. The main result is a quantizer design algorithm, and a proof that it finds the optimum quantizer in the partial problem. The quantizer design algorithm is based on a dynamic programming approach, and is an extension of a mutual-information maximization method. For the binary-input case, it is shown that the optimum quantizer can be found with complexity that is polynomial in the number of Channel outputs.

  • concatenation of a Discrete Memoryless Channel and a quantizer
    Information Theory Workshop, 2010
    Co-Authors: Brian M. Kurkoski, Hideki Yagi
    Abstract:

    The concatenation of an arbitrary Discrete Memoryless Channel with binary input followed by a quantizer is considered. For a restricted quantizer alphabet size, it is shown that the maximum of the mutual information between the Channel input and the quantizer output can be found by dynamic programming. Numerical examples are given to illustrate the results. This problem is shown to be an example of concave programming.

Tsachy Weissman - One of the best experts on this subject based on the ideXlab platform.

  • dude seq fast flexible and robust denoising for targeted amplicon sequencing
    PLOS ONE, 2017
    Co-Authors: Byunghan Lee, Taesup Moon, Sungroh Yoon, Tsachy Weissman
    Abstract:

    We consider the correction of errors from nucleotide sequences produced by next-generation targeted amplicon sequencing. The next-generation sequencing (NGS) platforms can provide a great deal of sequencing data thanks to their high throughput, but the associated error rates often tend to be high. Denoising in high-throughput sequencing has thus become a crucial process for boosting the reliability of downstream analyses. Our methodology, named DUDE-Seq, is derived from a general setting of reconstructing finite-valued source data corrupted by a Discrete Memoryless Channel and effectively corrects substitution and homopolymer indel errors, the two major types of sequencing errors in most high-throughput targeted amplicon sequencing platforms. Our experimental studies with real and simulated datasets suggest that the proposed DUDE-Seq not only outperforms existing alternatives in terms of error-correction capability and time efficiency, but also boosts the reliability of downstream analyses. Further, the flexibility of DUDE-Seq enables its robust application to different sequencing platforms and analysis pipelines by simple updates of the noise model. DUDE-Seq is available at http://data.snu.ac.kr/pub/dude-seq.

  • dude seq fast flexible and robust denoising for targeted amplicon sequencing
    arXiv: Genomics, 2015
    Co-Authors: Byunghan Lee, Taesup Moon, Sungroh Yoon, Tsachy Weissman
    Abstract:

    We consider the correction of errors from nucleotide sequences produced by next-generation targeted amplicon sequencing. The next-generation sequencing (NGS) platforms can provide a great deal of sequencing data thanks to their high throughput, but the associated error rates often tend to be high. Denoising in high-throughput sequencing has thus become a crucial process for boosting the reliability of downstream analyses. Our methodology, named DUDE-Seq, is derived from a general setting of reconstructing finite-valued source data corrupted by a Discrete Memoryless Channel and effectively corrects substitution and homopolymer indel errors, the two major types of sequencing errors in most high-throughput targeted amplicon sequencing platforms. Our experimental studies with real and simulated datasets suggest that the proposed DUDE-Seq not only outperforms existing alternatives in terms of error-correction capability and time efficiency, but also boosts the reliability of downstream analyses. Further, the flexibility of DUDE-Seq enables its robust application to different sequencing platforms and analysis pipelines by simple updates of the noise model. DUDE-Seq is available at this http URL

  • universal Discrete denoising known Channel
    International Symposium on Information Theory, 2003
    Co-Authors: Tsachy Weissman, Erik Ordentlich, G Seroussi, Sergio Verdu, M J Weinberger
    Abstract:

    A Discrete denoising algorithm estimates the input sequence to a Discrete Memoryless Channel (DMC) based on the observation of the entire output sequence. For the case in which the DMC is known and the quality of the reconstruction is evaluated with a given single-letter fidelity criterion, we propose a Discrete denoising algorithm that does not assume knowledge of statistical properties of the input sequence. Yet, the algorithm is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution, which is only assumed to be stationary. Moreover, the algorithm is universal also in a semi-stochastic setting, in which the input is an individual sequence, and the randomness is due solely to the Channel noise. The proposed denoising algorithm is practical, requiring a linear number of register-level operations and sublinear working storage size relative to the input data length.

  • tradeoffs between the excess code length exponent and the excess distortion exponent in lossy source coding
    IEEE Transactions on Information Theory, 2002
    Co-Authors: Tsachy Weissman, Neri Merhav
    Abstract:

    Lossy compression of a Discrete Memoryless source (DMS) with respect to a single-letter distortion measure is considered. We study the best attainable tradeoff between the exponential rates of the probabilities that the codeword length and that the cumulative distortion exceed respective thresholds for two main cases. The first scenario examined is that where the source is corrupted by a Discrete Memoryless Channel (DMC) prior to reaching the coder. In the second part of this work, we examine the universal setting, where the (noise-free) source is an unknown member P/sub /spl theta// of a given family {P/sub /spl theta//,/spl theta//spl isin//spl Theta/}. Here, inspired by an approach which was proven fruitful previously in the context of composite hypothesis testing, we allow the constraint on the excess-code-length exponent to be /spl theta/-dependent. Corollaries are derived for some special cases of interest, including Marton's (1974) classical source coding exponent and its generalization to the case where the constraint on the rate of the code is relaxed from an almost sure constraint to a constraint on the excess-code-length exponent.

Thuan Nguyen - One of the best experts on this subject based on the ideXlab platform.

  • on bounds and closed form expressions for capacities of Discrete Memoryless Channels with invertible positive matrices
    IEEE Transactions on Vehicular Technology, 2020
    Co-Authors: Thuan Nguyen, Thinh Nguyen
    Abstract:

    While capacities of Discrete Memoryless Channels are well studied, it is still not possible to obtain a closed-form expression for the capacity of an arbitrary Discrete Memoryless Channel (DMC). In this paper, we study a class of DMCs whose Channel matrix is an invertible positive matrix. This class of Channel matrices can be used to model many real-world settings. Next, an elementary technique based on Karush-Kuhn-Tucker (KKT) conditions is used to obtain (1) a good upper bound of a Discrete Memoryless Channel having an invertible positive Channel matrix and (2) a closed-form expression for the capacity if the Channel matrix satisfies certain conditions related to its singular value and its Gershgorin's disk.

  • on bounds and closed form expressions for capacities of Discrete Memoryless Channels with invertible positive matrices
    arXiv: Information Theory, 2020
    Co-Authors: Thuan Nguyen, Thinh Nguyen
    Abstract:

    While capacities of Discrete Memoryless Channels are well studied, it is still not possible to obtain a closed-form expression for the capacity of an arbitrary Discrete Memoryless Channel. This paper describes an elementary technique based on Karush Kuhn Tucker (KKT) conditions to obtain (1) a good upper bound of a Discrete Memoryless Channel having an invertible positive Channel matrix and (2) a closed-form expression for the capacity if the Channel matrix satisfies certain conditions related to its singular value and its Gershgorin disk.

  • on closed form capacities of Discrete Memoryless Channels
    Vehicular Technology Conference, 2018
    Co-Authors: Thuan Nguyen, Thinh Nguyen
    Abstract:

    While capacities of Discrete Memoryless Channels are well studied, it is still not possible to obtain a closed form expression of the capacity for an arbitrary Discrete Memoryless Channel. This paper shows an elementary technique based on Karush-Kuhn-Tucker (KKT) conditions to obtain a closed form expression for a good upper bound of an arbitrary Discrete Memoryless Channel. Furthermore, using this technique, we are able to obtain the closed form expressions for the capacities of Channels whose Channel matrices satisfy a number of conditions.

Vincent H Poor - One of the best experts on this subject based on the ideXlab platform.

  • capacity approaching polar codes with long codewords and successive cancellation decoding based on improved gaussian approximation
    IEEE Transactions on Communications, 2021
    Co-Authors: Hideki Ochiai, Patrick Mitran, Vincent H Poor
    Abstract:

    This paper focuses on an improved Gaussian approximation (GA) based construction of polar codes with successive cancellation (SC) decoding over an additive white Gaussian noise (AWGN) Channel. Arikan proved that polar codes with low-complexity SC decoding can approach the Channel capacity of an arbitrary symmetric binary-input Discrete Memoryless Channel, provided that the code length is chosen large enough. Nevertheless, how to construct such codes over an AWGN Channel with low computational effort has been an open problem. Compared to density evolution, the GA is known as a low complexity yet powerful technique that traces the evolution of the mean log likelihood ratio (LLR) value by iterating a nonlinear function. Therefore, its high-precision numerical evaluation is critical as the code length increases. In this work, by analyzing the asymptotic behavior of this nonlinear function, we propose an improved GA approach that makes an accurate trace of mean LLR evolution feasible. With this improved GA, through numerical analysis and simulations with code lengths up to $N=2^{18}$ , we explicitly demonstrate that various code-rate polar codes with long codeword and capacity approaching behavior can be easily designed.

  • capacity approaching polar codes with long codewords and successive cancellation decoding based on improved gaussian approximation
    arXiv: Information Theory, 2019
    Co-Authors: Hideki Ochiai, Patrick Mitran, Vincent H Poor
    Abstract:

    This paper focuses on an improved Gaussian approximation (GA) based construction of polar codes with successive cancellation (SC) decoding over an additive white Gaussian noise (AWGN) Channel. Arikan has proven that polar codes with low-complexity SC decoder can approach the Channel capacity of an arbitrary symmetric binary-input Discrete Memoryless Channel, provided that the code length is chosen large enough. Nevertheless, how to construct such codes over an AWGN Channel with low computational effort has been an open problem. Compared to density evolution, the GA is known as a low complexity yet powerful technique that traces the evolution of the mean log likelihood ratio (LLR) value by iterating a nonlinear function. Therefore, its high-precision numerical evaluation is critical as the code length increases. In this work, by analyzing the asymptotic behavior of this nonlinear function, we propose an improved GA approach that makes an accurate trace of mean LLR evolution feasible. With this improved GA, through numerical analysis and simulations with code lengths up to $N=2^{18}$, we explicitly demonstrate that various code-rate polar codes with long codeword and capacity approaching behavior can be easily designed.

  • secrecy reliability tradeoff for semi deterministic wiretap Channels at finite blocklength
    International Symposium on Information Theory, 2017
    Co-Authors: Wei Yang, Rafael F Schaefer, Vincent H Poor
    Abstract:

    This paper studies the maximum secrecy rate for a semi-deterministic wiretap Channel, in which the Channel between the transmitter and the legitimate receiver is deterministic, while that between the transmitter and the eavesdropper is a Discrete Memoryless Channel. For a given decoding error probability and information leakage (measured by the total variation distance), the optimal second-order secrecy rate is derived. Unlike the secrecy capacity, the second-order secrecy rate characterizes the optimal tradeoff between secrecy and reliability at finite blocklength.