Published Papers - KUZUOKA Shigeaki

Coding theorems for source coding with cost

Shigeaki Kuzuoka （Part： Lead author )

Proc. of 2024 International Symposium on Information Theory and its Applications     446 - 450   2024.11  [Refereed]

A study on the joint source-channel coding for computing functions: An approach from a dichotomy of functions

N. Joki, S. Kuzuoka （Part： Last author )

Proc. of 2021 IEEE Information Theory Workshop     2021.10  [Refereed]

Asynchronous guessing subject to distortion

Shigeaki Kuzuoka （Part： Lead author )

Proceedings of 2021 IEEE International Symposium on Information Theory     2008 - 2012   2021.07  [Refereed]

A study on the overflow probability of variable-to-fixed length codes

Shigeaki Kuzuoka （Part： Lead author,　Last author,　Corresponding author )

Proc. of 2020 International Symposium on Information Theory and its Applications     26 - 30   2020.10  [Refereed]

On the Conditional Smooth Rényi Entropy and its Applications in Guessing and Source Coding

Shigeaki Kuzuoka （Part： Lead author )

IEEE Transactions on Information Theory   66 ( 3 ) 1674 - 1690   2020.03  [Refereed]

A unified approach to error exponents for multiterminal source coding systems

Shigeaki Kuzuoka

IEICE Trans. Fundamentals     2018.12  [Refereed]

On Distributed Computing for Functions With Certain Structures

Shigeaki Kuzuoka, Shun Watanabe

IEEE TRANSACTIONS ON INFORMATION THEORY ( IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC )  63 ( 11 ) 7003 - 7017   2017.11  [Refereed]

　View Summary

The problem of distributed function computation is studied, where functions to be computed is not necessarily symbol-wise. A new method to derive a converse bound for distributed computing is proposed; from the structure of functions to be computed, information that is inevitably conveyed to the decoder is identified, and the bound is derived in terms of the optimal rate needed to send that information. The class of informative functions is introduced, and, for the class of smooth sources, the optimal rate for computing those functions is characterized. Furthermore, for sources with joint distribution that may not be full support, functions that are composition of symbol wise function and the type of a sequence are considered, and the optimal rate for computing those functions is characterized in terms of the hypergraph entropy. As a byproduct, our method also provides a conceptually simple proof of the known fact that computing a Boolean function may require as large rate as reproducing the entire source.

DOI

On Distributed Computing for Functions with Certain Structures

Shigeaki Kuzuoka, Shun Watanabe

2016 IEEE INFORMATION THEORY WORKSHOP (ITW) ( IEEE )    2016  [Refereed]

　View Summary

The problem of distributed function computation for the class of smooth sources is studied, where functions to be computed are compositions of symbol-wise functions and some outer functions that are not symbol-wise. The optimal rate for computing those functions is characterized in terms of the Slepian-Wolf rate and an equivalence class of sources induced by functions. To prove the result, a new method to derive a converse bound for distributed computing is proposed; the bound is derived by identifying a source that is inevitably conveyed to the decoder and by explicitly constructing a code for reproducing that source. As a byproduct, it provides a conceptually simple proof of the known fact that computing a Boolean function may require as large rate as reproducing the entire source.

Variable-Length Coding for Mixed Sources with Side Information Allowing Decoding Errors

Shigeaki Kuzuoka

PROCEEDINGS OF 2016 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2016) ( IEEE )    161 - 165   2016  [Refereed]

　View Summary

Variable-length source coding with side information allowing a nonzero decoding error probability epsilon is considered. For the case where the side information is available at both of the encoder and decoder, we give an explicit formula of the rate error function R-c(epsilon) for the mixture of i.i.d. sources. For the case where the side information is available only at the decoder, we concentrate our attention on the mixture of binary symmetric sources. Our result gives a simple way to draw the graph of the rate-error function R(epsilon).

The Error Exponent of Zero-Rate Multiterminal Hypothesis Testing for Sources with Common Information

Makoto Ueda, Shigeaki Kuzuoka （Part： Last author )

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES ( IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG )  E98A ( 12 ) 2384 - 2392   2015.12  [Refereed]

　View Summary

The multiterminal hypothesis testing problem with zerorate constraint is considered. For this problem, an upper bound on the optimal error exponent is given by Shalaby and Papamarcou, provided that the positivity condition holds. Our contribution is to prove that Shalaby and Papamarcou's upper bound is valid under a weaker condition: (i) two remote observations have a common random variable in the sense of Gacks and Korner, and (ii) when the value of the common random variable is fixed, the conditional distribution of remaining random variables satisfies the positivity condition. Moreover, a generalization of the main result is also given.

DOI

A Dichotomy of Functions in Distributed Coding: An Information Spectral Approach

Shigeaki Kuzuoka, Shun Watanabe

IEEE TRANSACTIONS ON INFORMATION THEORY ( IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC )  61 ( 9 ) 5028 - 5041   2015.09  [Refereed]

　View Summary

The problem of distributed data compression for function computation is considered, where: 1) the function to be computed is not necessarily symbolwise function and 2) the information source has memory and may not be stationary nor ergodic. We introduce the class of smooth sources and give a sufficient condition on functions so that the achievable rate region for computing coincides with the Slepian-Wolf region (i.e., the rate region for reproducing the entire source) for any smooth sources. Moreover, for symbolwise functions, the necessary and sufficient condition for the coincidence is established. Our result for the full side-information case is a generalization of the result by Ahlswede and Csiszar to sources with memory; our dichotomy theorem is different from Han and Kobayashi's dichotomy theorem, which reveals an effect of memory in distributed function computation. All results are given not only for fixed-length coding but also for variable-length coding in a unified manner. Furthermore, for the full side-information case, the error probability in the moderate deviation regime is also investigated.

DOI

An Information-Spectrum Approach to Weak Variable-Length Source Coding With Side-Information

Shigeaki Kuzuoka, Shun Watanabe

IEEE TRANSACTIONS ON INFORMATION THEORY ( IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC )  61 ( 6 ) 3559 - 3573   2015.06  [Refereed]

　View Summary

This paper studies variable-length (VL) source coding of general sources with side-information. Novel one-shot coding bounds for Slepian-Wolf (SW) coding, which give nonasymptotic tradeoff between the error probability and the codeword length of VL-SW coding, are established. One-shot results are applied to asymptotic analysis, and a general formula for the optimal coding rate achievable by weakly lossless VL-SW coding (i.e., VL-SW coding with vanishing error probability) is derived. Our general formula reveals how the encoder side-information and/or VL coding improve the optimal coding rate in the general setting. In addition, it is shown that if the encoder side-information is useless in weakly lossless VL coding then it is also useless even in the case where the error probability may be positive asymptotically.

DOI

Nonasymptotic and Second-Order Achievability Bounds for Coding With Side-Information

Shun Watanabe, Shigeaki Kuzuoka, Vincent Y. F. Tan

IEEE TRANSACTIONS ON INFORMATION THEORY ( IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC )  61 ( 4 ) 1574 - 1605   2015.04  [Refereed]

　View Summary

We present a novel nonasymptotic or finite blocklength achievability bounds for three side-information problems in network information theory. These include: 1) the Wyner-Ahlswede-Korner (WAK) problem of almost-lossless source coding with rate-limited side-information; 2) the Wyner-Ziv (WZ) problem of lossy source coding with side-information at the decoder; and 3) the Gel'fand-Pinsker (GP) problem of channel coding with noncausal state information available at the encoder. The bounds are proved using ideas from channel simulation and channel resolvability. Our bounds for all three problems improve on all previous nonasymptotic bounds on the error probability of the WAK, WZ, and GP problems-in particular those derived by Verdu. Using our novel nonasymptotic bounds, we recover the general formulas for the optimal rates of these side-information problems. Finally, we also present achievable second-order coding rates by applying the multidimensional Berry-Esseen theorem to our new nonasymptotic bounds. Numerical results show that the second-order coding rates obtained using our nonasymptotic achievability bounds are superior to those obtained using existing finite blocklength bounds.

DOI

A Dichotomy of Functions in Distributed Coding: An Information Spectral Approach

Shigeaki Kuzuoka, Shun Watanabe

2015 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) ( IEEE )    1766 - 1770   2015  [Refereed]

　View Summary

The problem of distributed data compression for function computation is considered, where (i) the function to be computed is not necessarily symbol-wise function and (ii) the information source has memory and may not be stationary nor ergodic. We introduce the class of smooth sources and give a sufficient condition on functions so that the achievable rate region for computing coincides with the Slepian-Wolf region (i.e., the rate region for reproducing the entire source) for any smooth sources. Moreover, for symbol-wise functions, the necessary and sufficient condition for the coincidence is established. Our result for the full side-information case is a generalization of the result by Ahlswede and Csiszar; our dichotomy theorem is different from Han and Kobayashi's dichotomy theorem, which reveals an effect of memory in distributed function computation. All results are given not only for fixed-length coding but also for variable-length coding in a unified manner.

Universal Wyner-Ziv Coding for Distortion Constrained General Side Information

Shun Watanabe, Shigeaki Kuzuoka

IEEE TRANSACTIONS ON INFORMATION THEORY ( IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC )  60 ( 12 ) 7568 - 7583   2014.12  [Refereed]

　View Summary

We investigate the Wyner-Ziv coding in which the statistics of the principal source is known but the statistics of the channel generating the side information is unknown except that it is in a certain class. The class consists of channels such that the distortion between the principal source and side information is smaller than a threshold, but channels may be neither stationary nor ergodic. In this situation, we define a new rate-distortion function as the minimum rate such that there exists a Wyner-Ziv code that is universal for every channel in the class. Then, we show an upper bound and a lower bound on the rate-distortion function, and derive a matching condition such that the upper and lower bounds coincide. The relation between the new rate-distortion function and rate-distortion function of the Heegard-Berger problem is also discussed.

DOI

An Information-Spectrum Approach to Weak Variable-Length Slepian-Wolf Coding

Shigeaki Kuzuoka, Shun Watanabe

2014 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) ( IEEE )    2684 - 2688   2014  [Refereed]

　View Summary

In this paper, we investigate weak variable-length Slepian-Wolf (VL-SW) coding of general sources. First, by using the information-spectrum method, we show novel non-asymptotic trade-off between the error probability and the codeword length of VL-SW coding. Then, we give an asymptotic formula for the optimal coding rate achievable by VL-SW coding. Especially, we investigate VL-SW coding for mixed sources. Our results spotlights the fact that distinguishability between component sources plays an important role in adjusting the coding rate at the encoder. We also demonstrate that our general results derive a known formula for the optimal achievable rate of VL-SW coding for mixture of i.i.d. sources and extend to countably infinite alphabet case with mild condition.

Universal Wyner-Ziv coding for distortion constrained general side-information

Shun Watanabe, Shigeaki Kuzuoka

IEEE International Symposium on Information Theory - Proceedings     1357 - 1361   2013  [Refereed]

　View Summary

We investigate the Wyner-Ziv coding in which the statistics of the principal source is known but the statistics of the channel generating the side-information is unknown except that it is in a certain class. The class consists of channels such that the distortion between the principal source and the side-information is smaller than a threshold, but channels may be neither stationary nor ergodic. In this situation, we define a new rate-distortion function as the minimum rate such that there exists a Wyner-Ziv code that is universal for every channel in the class. Then, we show an upper bound and a lower bound on the rate-distortion function, and derive a matching condition such that the upper and lower bounds coincide. © 2013 IEEE.

DOI

Non-asymptotic and second-order achievability bounds for source coding with side-information

Shun Watanabe, Shigeaki Kuzuoka, Vincent Y.F. Tan

IEEE International Symposium on Information Theory - Proceedings     3055 - 3059   2013  [Refereed]

　View Summary

We present a novel achievability bound for the Wyner-Ahlswede-Körner (WAK) problem of lossless source coding with rate-limited side-information. This bound is proved using ideas from channel simulation and channel resolvability. The bound improves on all previous non-asymptotic bounds on the error probability of the WAK problem. We also present achievable second-order coding rates by applying the multidimensional Berry-Essèen theorem to our new non-asymptotic bound. © 2013 IEEE.

DOI

A Sufficient Condition for the Existence of a Universal Slepian-Wolf Code

Shigeaki Kuzuoka

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES ( IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG )  E93A ( 7 ) 1355 - 1362   2010.07  [Refereed]

　View Summary

Universal Slepian-Wolf coding for parametric general sources is considered. Our main result shows that under mild conditions on the family of sources, there exists a universal decoder that attains asymptotically the same random-coding error exponent as the maximum-likelihood decoder.

DOI

Universal Source Coding for Multiple Decoders with Side Information

Shigeaki Kuzuoka, Akisato Kimura, Tomohiko Uyematsu

2010 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY ( IEEE )    1 - 5   2010  [Refereed]

　View Summary

A multiterminal lossy source coding problem, which includes various problems such as the Wyner-Ziv problem and the complementary delivery problem as special cases, is considered. It is shown that any point in the achievable rate-distortion region can be attained even if the source statistics are not known.

Slepian-Wolf Coding of Individual Sequences Based on Ensembles of Linear Functions

Shigeaki Kuzuoka

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES ( IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG )  E92A ( 10 ) 2393 - 2401   2009.10  [Refereed]

　View Summary

This paper clarifies the adequacy of the linear channel coding approach for Slepian-Wolf coding of individual sequences. A sufficient condition for ensembles of linear codes from which a universal Slepian-Wolf code can be constructed is given. Our result reveals that an ensemble of LDPC codes gives a universal code for Slepian-Wolf coding of individual sequences.

DOI

Universal source coding over generalized complementary delivery networks

Akisato Kimura, Tomohiko Uyematsu, Shigeaki Kuzuoka, Shun Watanabe

IEICE Trans. Fundamentals     2009.03  [Refereed]

On the Suboptimality of Linear Lossy Codes

Shigeaki Kuzuoka

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES ( IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG )  E91A ( 10 ) 2868 - 2869   2008.10  [Refereed]

　View Summary

This letter reveals that linear lossy codes cannot attain the rate-distortion function in general, even if the source is binary i.i.d. and the distortion is measured by the Hamming distortion measure.

DOI

An application of linear codes to the problem of source coding with partial side information

Shigeaki Kuzuoka

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES ( IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG )  E91A ( 8 ) 2151 - 2158   2008.08  [Refereed]

　View Summary

This paper clarifies the adequacy of the linear channel coding approach for the source coding with partial side information at the decoder. A sufficient condition for an ensemble of linear codes which achieves the Wyner's bound is given. Our result reveals that, by combining a good lossy code, an LDPC code ensemble gives a good code for source coding with partial side information at the decoder.

DOI

Fixed-slope universal lossy coding for individual sequences and nonstationary sources

Shigeaki Kuzuoka, Tomohiko Uyematsu

IEICE Trans. Fundamentals     2008.03  [Refereed]

Universal lossy coding for individual sequences based on complexity functions

Shigeaki Kuzuoka, Tomohiko Uyematsu

IEICE Trans. Fundamentals     2007.02  [Refereed]

Universal coding for correlated sources with complementary delivery

Akisato Kimura, Tomohiko Uyematsu, Shigeaki Kuzuoka

IEICE Trans. Fundamentals ( IEEE )  E90-A ( 2 ) 1840 - 1847   2007  [Refereed]

　View Summary

This report deals with a universal coding problem for a certain kind of multiterminal source coding system that we call the complementary delivery coding system. Both fixed-to-fixed length and fixed-to-variable length lossless coding schemes are considered. Explicit constructions of universal codes and the bounds of the error probabilities are clarified via type-theoretical and graph-theoretical analyses.

Relationship among complexities of individual sequences over countable alphabet

Shigeaki Kuzuoka, Tomohiko Uyematsu

IEICE Trans. Fundamentals     2006.07  [Refereed]

Fixed-slope universal lossy coding for individual sequences

Shigeaki Kuzuoka, Tomohiko Uyematsu

PROCEEDINGS OF 2006 IEEE INFORMATION THEORY WORKSHOP ( IEEE )    244 - +   2006  [Refereed]

　View Summary

In a theory of lossy coding of individual sequences, two kinds of coding schemes, the fixed-rate coding and the fixed-distortion coding, have been studied. This paper investigates another kind of lossy coding scheme of individual sequences, which is called fixed-slope lossy coding. We show that the optimal cost attainable by the blockwise fixed-slope lossy encoder is equal to the optimal average cost with respect to the overlapping empirical distribution of the given sequence. Moreover, we clarify that the fixed-slope universal lossy block encoder based on the complexity function achieves the optimal cost. As an application of the result, we show that for any ergodic source the sample average of the cost achieved by the lossy block encoder based on the complexity function is asymptotically equal to the optimal cost with probability one.

Applicability of the sample path method of ergodic processes to individual sequences

S Kuzuoka, T Uyematsu

2004 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, PROCEEDINGS ( IEEE )    561 - 561   2004  [Refereed]

　View Summary

This paper proposes a method which enables to apply some results on ergodic sources to individual sequences. As an example, we show the recurrence time theorem for individual sequences.

Conditional Lempel-Ziv complexity and its application to source coding theorem with side information

T Uyematsu, S Kuzuoka

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES ( IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG )  E86A ( 10 ) 2615 - 2617   2003.10  [Refereed]

　View Summary

This paper proposes the conditional LZ complexity and analyzes its property. Especially, we show an inequality corresponding to Ziv's inequality concerning a distinct parsing of a pair of sequences. Further, as a byproduct of the result, we show a simple proof of the asymptotical optimality of Ziv's universal source coding algorithm with side information.