This paper deals with two typical random number generation problems in information theory. One is the source resolvability problem (resolvability problem for short) and the other is the intrinsic randomness problem. In the literature, optimum achievable rates in these two problems with respect to the variational distance as well as the Kullback-Leibler (KL) divergence have already been analyzed. On the other hand, in this study we consider these two problems with respect to f-divergences. The f-divergence is a general non-negative measure between two probabilistic distributions on the basis of a convex function f. The class of f-divergences includes several important measures such as the variational distance, the KL divergence, the Hellinger distance and so on. Hence, it is meaningful to consider the random number generation problems with respect to f-divergences. In this paper, we impose some conditions on the function f so as to simplify the analysis, that is, we consider a subclass of f-divergences. Then, we first derive general formulas of the first-order optimum achievable rates with respect to f-divergences. Next, we particularize our general formulas to several specified functions f. As a result, we reveal that it is easy to derive optimum achievable rates for several important measures from our general formulas. The second-order optimum achievable rates and optimistic optimum achievable rates have also been investigated.

This paper addresses the problem of selecting a significant subset of candidate features to use for multiple linear regression. Bertsimas et al. [5] recently proposed the discrete first-order (DFO) algorithm to efficiently find near-optimal solutions to this problem. However, this algorithm is unable to escape from locally optimal solutions. To resolve this, we propose a stochastic discrete first-order (SDFO) algorithm for feature subset selection. In this algorithm, random perturbations are added to a sequence of candidate solutions as a means to escape from locally optimal solutions, which broadens the range of discoverable solutions. Moreover, we derive the optimal step size in the gradient-descent direction to accelerate convergence of the algorithm. We also make effective use of the L-2-regularization term to improve the predictive performance of a resultant subset regression model. The simulation results demonstrate that our algorithm substantially outperforms the original DFO algorithm. Our algorithm was superior in predictive performance to lasso and forward stepwise selection as well.

Lossless variable-length source coding with codeword cost is considered for general sources. The problem setting, where we impose on unequal costs on code symbols, is called the variable-length coding with codeword cost. In this problem, the infimum of average codeword cost have already been determined for general sources. On the other hand, the overflow probability, which is defined as the probability of codeword cost being above a threshold, have not been considered yet. In this paper, we first determine the infimum of achievable threshold in the first-order sense and the second-order sense for general sources with additive memoryless codeword cost. Then, we compute it for some special sources such as i.i.d. sources and mixed sources. A generalization of the codeword cost is also discussed.

The variable-length source coding problem allowing the error probability up to some constant is considered for general sources. In this problem, the optimum mean codeword length of variable-length codes has already been determined. On the other hand, in this paper, we focus on the overflow (or excess codeword length) probability instead of the mean codeword length. The infimum of overflow thresholds under the constraint that both of the error probability and the overflow probability are smaller than or equal to some constant is called the optimum overflow threshold. In this paper, we first derive finite-length upper and lower bounds on these probabilities so as to analyze the optimum overflow thresholds. Then, by using these bounds, we determine the general formula of the optimum overflow thresholds in both of the first-order and second-order forms. Next, we consider another expression of the derived general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem. Finally, we apply the general formula derived in this paper to the case of stationary memoryless sources.

This paper deals with the source resolvability problem which is one of typical random number generation problems. In the literatures, the achievable rate in the source resolvability problem with respect to the variational distance as well as the Kullback-Leibler (KL) divergence have been analyzed. On the other hand, in this study we consider the problem with respect to a subclass of f-divergence. The f-divergence is a general non-negative measure between two probabilistic distributions and includes several important measures such as the variational distance, the KL divergence, the Hellinger distance and so on. Hence, it is meaningful to consider the source resolvability problem with respect to the f-divergence. We derive the general formula of the optimum achievable rate for a certain subclass of the f-divergence. Then, we reveal that it is easy to derive previous results from our general formula.

This paper deals with the intrinsic randomness (IR) problem, which is one of typical random number generation problems. In the literature, the optimum achievable rates in the IR problem with respect to the variational distance as well as the Kullback-Leibler (KL) divergence have already been analyzed. On the other hand, in this study we consider the IR problem with respect to a subclass of f-divergences. The f-divergence is a general non-negative measure between two probabilistic distributions and includes several important measures such as the total variational distance, the chi(2)-divergence, the KL divergence, and so on. Hence, it is meaningful to consider the IR problem with respect to the f-divergence. In this paper, we assume some conditions on the f-divergence for simplifying the analysis. That is, we focus on a subclass of f-divergences. In this problem setting, we first derive the general formula of the optimum achievable rate. Next, we show that it is easy to derive the optimum achievable rate with respect to the variational distance, the KL divergence, and the Hellinger distance from our general formula.

A homeomorphically irreducible spanning tree (HIST) of a graph G is a spanning tree without vertices of degree 2 in G. Malkevitch conjectured that every 4-connected plane graph has a HIST. In order to solve Malkevitch-conjecture, it is natural to show the existence of a HIST in 3-connected, internally 4-connected (or essentially 4 connected) plane graphs. In this paper, we construct 3-connected, internally 4-connected plane graphs without HISTs. Consequently, such a strategy does not work when we solve Malkevitch-conjecture.

The first- and second-order optimum achievable exponents in the simple hypothesis testing problem are investigated. The optimum achievable exponent for type II error probability, under the constraint that the type I error probability is allowed asymptotically up to e, is called the s-optimum exponent. In this paper, we first give the second-order s-optimum exponent in the case where the null hypothesis and alternative hypothesis are a mixed memoryless source and a stationary memoryless source, respectively. We next generalize this setting to the case where the alternative hypothesis is also a mixed memoryless source. Secondly, we address the first-order s-optimum exponent in this setting. In addition, an extension of our results to the more general setting such as hypothesis testing with mixed general source and a relationship with the general compound hypothesis testing problem are also discussed.

The variable-length coding problem allowing the error probability up to some constant is considered for general sources. In this problem, we focus on the overflow (or excess codeword length) probability We also consider another expression of our general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem.

The first- and second-order optimum achievable rates in the source resolvability problem are considered for general sources. In the literature, the achievable rates in the resolvability problem with respect to the variational distance as well as the normalized Kullback-Leibler (KL) divergence have already been analyzed. On the other hand, in this study we consider the source resolvability problem with respect to (unnormalized) KL divergence and derive general formulas of the first- and second-order optimum achievable rates. Relationships with other problems in information theory have also been discussed.

The variable-length source coding with unequal cost allowing error probability is considered for general sources. In this setting, the first-and second-order optimum mean codeword cost have already been determined. On the other hand, we focus on the overflow probability of codeword cost and determine the general formulas of the first-and second-order optimum achievable overflow threshold. We also apply our general formulas to the stationary memoryless source.

We consider fixed-to-variable length coding with a regular cost function by allowing the error probability up to any constant epsilon. We first derive finite-length upper and lower bounds on the average codeword cost, which are used to derive general formulas of two kinds of minimum achievable rates. For a fixed-to-variable length code, we call the set of source sequences that can be decoded without error the dominant set of source sequences. For any two regular cost functions, it is revealed that the dominant set of source sequences for a code attaining the minimum achievable rate under a cost function is also the dominant set for a code attaining the minimum achievable rate under the other cost function. We also give general formulas of the second-order minimum achievable rates.

The first- and second-order optimum achievable exponents in the simple hypothesis testing problem are investigated. The optimum achievable exponent for type II error probability, under the constraint that the type I error probability is allowed asymptotically up to epsilon, is called the epsilon-optimum exponent. In this paper, we first give the second-order epsilon-exponent in the case where the null hypothesis and the alternative hypothesis are a mixed memoryless source and a stationary memoryless source, respectively. We next generalize this setting to the case where the alternative hypothesis is also a mixed memoryless source. We address the first- order epsilon-optimum exponent in this setting.

The variable-length coding problem allowing the error probability up to some constant is considered for general sources. In this problem, we focus on the overflow (or excess codeword length) probability We also consider another expression of our general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem.

This paper investigates the first-and second-order maximum achievable rates of codes with/without cost constraints for mixed channels whose channel law is characterized by a general mixture of (at most) uncountably many stationary and memoryless discrete channels. These channels are referred to as mixed memoryless channels with general mixture and include the class of mixed memoryless channels of finitely or countably memoryless channels as a special case. For the mixed memoryless channels with general mixture, the first-order coding theorem which gives a formula for the e-capacity is established, and then a direct part of the second-order coding theorem is provided. A subclass of mixed memoryless channels whose component channels can be ordered according to their capacity is introduced, and the first-and second-order coding theorems are established. It is shown that the established formulas reduce to several known formulas for restricted scenarios.

We consider a new concept of achievability in the variable-length lossy source coding on the basis of the probability of the union of the overflow of codeword length and the excess distortion. In this setting, our main concern is to determine the achievable rate-distortion region for a given source and distortion measure. To this end, we first derive non-asymptotic upper and lower bounds, and then we derive general formulas of this achievable rate-distortion region in the first- and second-order sense. Finally, we apply our general formulas to stationary memoryless sources with an additive distortion measure.

We derive a general formula of the minimum achievable rate for fixed-to-variable length coding with a regular cost function by allowing the error probability up to a constant. E. For a fixed-to-variable length code, we call the set of source sequences that can be decoded without error the dominant set of source sequences. For any two regular cost functions, it is revealed that the dominant set of source sequences for a code attaining the minimum achievable rate with a cost function is also the dominant set for a code attaining the minimum achievable rate with the other cost function. We also give a general formula of the second-order minimum achievable rate.

共同研究により担当分抽出不可能．指導および構成を担当

This paper addresses two problems of variable length coding with a fidelity criterion for general sources, in which either the probability of codeword length overflow or that of excess distortion for a given threshold is allowed up to epsilon. In each problem, a general formula for the achievable region of coding rates and distortion levels is established via information spectrum methods. It is shown that there is a tight connection between the two problems, and the achievable regions are the same under a mild condition on the distortion measure. As a consequence, it turns out that superficially different general formulas for the two coding problems coincide with each other.

This paper deals with a fixed-length lossy source coding problem with some excess distortion probability called the source coding problem with epsilon-fidelity criterion. In this problem, the rate-distortion function and the distortion-rate function have already been characterized for i.i.d. sources with an additive distortion measure in the sense of first-order and second-order coding rates. However, general formulas for these functions have not been revealed up to present. Hence, in this paper we derive general formulas for the rate-distortion function and the distortion-rate function with the epsilon-fidelity criterion in both of the first-order and second-order cases. A relationship between our general formulas and previous results are also discussed.

This paper studies the first- and second-order maximum achievable rates of codes with/without cost constraints for general mixed channels whose channel law is characterized by a mixture of uncountably many stationary and memoryless discrete channels. These channels are referred to as general mixed memoryless channels and include mixed memoryless channels of finitely or countably many memoryless channels as a special case. For general mixed memoryless channels, the first-order coding theorem which gives a formula for the epsilon-capacity is established, and then a direct part of the second-order coding theorem is provided. A subclass of general mixed memoryless channels whose component channels can be ordered according to their capacity is introduced, and the first- and second-order coding theorems are established. It is shown that the established formulas reduce to several known formulas for restricted scenarios.

The second-order achievable rate region in Slepian-Wolf source coding systems is investigated. The concept of second-order achievable rates, which enables us to make a finer evaluation of achievable rates, has already been introduced and analyzed for general sources in the single-user source coding problem. Analogously, in this paper, we first define the second-order achievable rate region for the Slepian-Wolf coding system to establish the source coding theorem in the second-order sense. The Slepian-Wolf coding problem for correlated sources is one of typical problems in the multiterminal information theory. In particular, Miyake and Kanaya, and Han have established the first-order source coding theorems for general correlated sources. On the other hand, in general, the second-order achievable rate problem for the Slepian-Wolf coding system with general sources remains still open up to present. In this paper, we present the analysis concerning the second-order achievable rates for general sources, which are based on the information spectrum methods developed by Han and Verdu. Moreover, we establish the explicit second-order achievable rate region for independently and identically distributed (i.i.d.) correlated sources with countably infinite alphabets and mixtures of i.i.d. correlated sources, respectively, using the relevant asymptotic normality.

For the class of mixed channels decomposed into stationary memoryless channels, single-letter characterizations of the epsilon-capacity have not been known except for restricted classes of channels such as the regular decomposable channel introduced by Winkelbauer. This paper gives single-letter characterizations of epsilon-capacity for mixed channels decomposed into at most countably many memoryless channels with a finite input alphabet with/without cost constraints. It is shown that the given characterization reduces to the one for the channel capacity given by Ahlswede when epsilon is zero. Some properties of the function of the epsilon-capacity are analyzed.

For a class of mixed channels that are decomposed into finitely many stationary memoryless channels, the optimum second-order coding rate, or equivalently, channel dispersion, is derived. The addressed channel, which is an instance of non-ergodic channels, is a sub-class of regular decomposable channels introduced by Winkelbauer. The second-order coding theorem can be viewed as an extension of the coding theorem established by Polyanskiy, Poor, and Verdu for the mixed channel of finitely many binary symmetric channels.

The second-order achievable asymptotics in typical random number generation problems such as resolvability, intrinsic randomness, and fixed-length source coding are considered. In these problems, several researchers have derived the first-order and the second-order achievability rates for general sources using the information spectrum methods. Although these formulas are general, their computations are quite hard. Hence, an attempt to address explicit computation problems of achievable rates is meaningful. In particular, for i.i.d. sources, the second-order achievable rates have earlier been determined simply by using the asymptotic normality. In this paper, we consider mixed sources of two i.i.d. sources. The mixed source is a typical case of non-ergodic sources and whose self-information does not have the asymptotic normality. Nonetheless, we can explicitly compute the second-order achievable rates for these sources on the basis of two-peak asymptotic normality. In addition, extensions of our results to more general mixed sources, such as a mixture of countably infinite i.i.d. sources or Markov sources, and a continuous mixture of i.i.d. sources, are considered.

The second-order achievable rate region in Slepian-Wolf source coding systems is investigated. The concept of second-order achievable rates, which enables us to make a finer evaluation of achievable rates, has already been introduced and analyzed for general sources in the single-user source coding problem. Accordingly, in this paper, we first define the second-order achievable rate region for the Slepian-Wolf coding system and establish the source coding theorem for general sources in the second-order sense. Moreover, we compute the explicit second-order achievable rate region for i.i.d. correlated sources with countably infinite alphabets and mixed correlated sources, respectively, using the relevant asymptotic normality.

Lossless variable-length source coding with unequal cost function is considered for general sources. In this problem, the codeword cost instead of codeword length is important. The infimum of average codeword cost has already been determined for general sources. We consider the overflow probability of codeword cost and determine the infimum of achievable overflow threshold. Our analysis is on the basis of information-spectrum methods and hence valid through the general source.

The second-order achievable rates in typical random number generation problems are considered. In these problems, several researchers have derived the first-order and the second-order achievability rates for general sources using the information spectrum methods. Although these formulas are general, their computation are quite hard. Hence, an attempt to address explicit computation problems of achievable rates is meaningful. In this paper, we consider mixed sources of two i.i.d. sources and compute the second-order achievable rates explicitly.

Source coding theorem reveals the minimum achievable code length under the condition that the error probability is smaller than or equal to some small constant. In the single user communication system, the source coding theorem was proved for general sources. The class of general source is quite large and it is important result since the result can be applied for a wide class of sources. On the other hand there are several studies to evaluate the achievable code length more precisely for the restricted class of sources by using the restriction. In the multi-user communication system, although the source coding theorem was proved for general correlated sources, there is no study to evaluate the achievable code length more precisely. In this study, we consider the stationary memoryless correlated sources and show the coding theorem for Slepian-Wolf type problem more precisely than the previous result.

The overflow probability is one of criteria that evaluate the performance of fixed-to-variable length (FV) codes. In the single source coding problem, there were many researches on the overflow probability. Recently, the source coding problem for correlated sources, such as Slepian-Wolf coding problem or source coding problem with side information, is one of main topics in information theory. In this paper, we consider the source coding problem with side information. In particular, we consider the FV code in the case that the encoder and the decoder can see side information. In this case, several codes were proposed and their mean code lengths were analyzed. However, there was no research about the overflow probability. We shall show two lemmas about the overflow probability. Then we obtain the condition that there exists a FV code under the condition that the overflow probability is smaller than or equal to some constant.

情報源Resolvability問題とは,任意に与えられた情報源に対して,可能な限り小さなサイズの一様乱数を用いてその情報源を近似する問題である.本研究では定常無記憶情報源を対象として,近似誤差(Kullback-Leibler情報量)が一定値以内となるために必要な一様乱数のサイズの条件について考察する.

We consider the source coding problem with side information. Especially, we consider the FV code in the case that the encoder and the decoder can see side information. We obtain the condition that there exists a FV code under the condition that the overflow probability is smaller than or equal to some constant.

Lossless fixed-to-variable(FV) length codes are considered. The overflow probability is one of criteria that evaluate the performance of FV code. In the single source coding problem, there were many researches on the overflow probability. Recently, the source coding problem for correlated sources, such as Slepian-Wolf coding problem or source coding problem with side information, is one of main topics in information theory. In this paper, we consider the source coding problem with side information. Especially, we consider the FV code in the case that the encoder and the decoder can see side information. In this case, several codes were proposed and their mean code lengths were analyzed. However, there was no research about the overflow probability. We shall show two lemmas about the overflow probability. Then we obtain the condition that there exists a FV code under the condition that the overflow probability is smaller than or equal to some constant.

The joint source-channel coding problem is considered. The joint source-channel coding theorem reveals the existence of a code for the pair of the source and the channel under the condition that the error probability is smaller than or equal to epsilon asymptotically. The separation theorem guarantees that we can achieve the optimal coding performance by using the two-stage coding. In the case that epsilon = 0, Han showed the joint source-channel coding theorem and the separation theorem for general sources and channels. Furthermore the epsilon-coding theorem (0 <= epsilon < 1) in the similar setting was studied. However, the separation theorem was not revealed since it is difficult in general. So we consider the separation theorem in this setting.

In this study, we consider a joint source-channel coding problem. The joint source-channel coding theorem reveals the existence of a code for the pair of the source V and the channel W under the condition that the probability of error is smaller than or equal to E asymptotically. We show the separation theorem for general sources and general channels.

In this letter, we generalize the achievability of variable-length coding from two viewpoints. One is the definition of an overflow probability, and the other is the definition of an achievability. We define the overflow probability as the probability of codeword length, not per symbol, is larger than eta(n) and we introduce the epsilon-achievability of variable-length codes that implies an existence of a code for the source under the condition that the overflow probability is smaller than or equal to epsilon. Then we show that the epsilon-achievability of variable-length codes is essentially equivalent to the epsilon-achievability of fixed-length codes for general sources. Moreover by using above results, we show the condition of epsilon-achievability for some restricted sources given epsilon.

担当：1-6章(14/14頁)／現在の圧縮アルゴリズム（符号）の性能評価には主に平均符号長に基づいて行われてきた。JPEG2000にも採用されている算術符号も、平均符号長の点から考えて高性能な符号である。平均符号長とはその符号を用いて符号化した際の符号化後の平均的な長さを表しており、その符号の平均的な性能を表している。一方、センサーネットワーク等への応用を考えた際にはアルゴリズムの平均的な性能の評価のみでは不十分であると言われており、様々な評価基準が提案されている。オーバーフロー確率もその一つであり、平均的な性能ではなく、その符号にとって悪条件の場合の性能を表している。本研究では、各種符号のオーバーフロー確率を理論的に評価した。対象とした符号の中には、平均符号長の意味で最適な符号も含まれており、現在実用化されている符号のオーバーフロー確率を評価したと考えられる。この結果は実用化対象の符号を理論的な側面から評価した

In this paper, we generalize the achievability of variable-length coding from two viewpoints. One is the definition of an overflow probability, and the other is the definition of an achievability. We define the overflow probability as the probability of codeword length, not per symbol, is larger than eta(n) and we introduce the epsilon-achievability of variable-length codes that implies an existence of a code for the source under the condition that the overflow probability is smaller than or equal to epsilon.Then we show that the epsilon-achievabitity of variable-length codes is essentially equivalent to the epsilon-achievability of fixed-length codes for general sources. Moreover we show the condition of epsilon-achievability for some restricted sources given epsilon.

担当：1-5章(14/14頁)／現在、zipやlzhとして実用化されている圧縮ソフトウェアは1970年代後半に提案されたLZアルゴリズムが元となっている。一方1990年代後半に理論上はその性能を上回るアルゴリズムが提案されており、実用化が待たれている。しかし、そのベイズ符号化アルゴリズムは（時間）計算量にいては効率的であるものの必要とするメモリ容量（空間計算量）がデータ長に対して指数的に増えるという欠点を持っていた。本論文では、ベイズ符号化アルゴリズムの実用化に向けてメモリ容量を低減した近似アルゴリズムを提案した。さらに提案したアルゴリズムの圧縮性能について理論と実験の双方から評価した。従来、この分野では実用化に向けてメモリ容量の問題点を改善したアルゴリズムの提案はされていたが、提案のみで理論的な評価が行われている研究はほとんどんない。すなわち、本研究は理論的な性能評価と実用化への課題を双方行っているという意味で非常に意味

雑音が混入した観測信号から未知の信号を推定する問題において,正規直交基底を用いた推定法が従来から研究されている.本研究では,ウェーブレットパケット基底の集合を用いて推定を行う場合の問題設定を扱う.従来においては,この問題設定においてベイズ的手法の適用が試みられているものの,未知信号と推定信号の間の2乗誤差を損失関数とした場合のベイズ最適な推定に関しては考察されていなかった.本研究では2乗誤差損失のもとでのベイズ最適な推定量,推定信号を効率的に計算するアルゴリズムを提案し,推定量の性能と性質に関して考察する.

In this paper, we show the probability of length overflow of several codes by using the variance and the asymptotic normality of the codelength.