As claimed in International Telecommunications Union (ITU) Recommendation ITU-R M.2160, 6G communication systems require extremely high-security and low-latency communication, necessitating the study of covert communication operating at finite blocklengths. In the point-to-point (P2P) setting, covert communication enables a transmitter to send messages reliably over a noisy channel to a legitimate receiver without being detected by any third party. Under the covertness metric of Kullback–Leibler divergence (KLD), we derive exact second-order asymptotics for P2P covert communication over a multiple-input multiple-output (MIMO) additive white Gaussian noise (AWGN) channel. In particular, our theoretical benchmarks refine the first-order asymptotics of Wang and Bloch (TIFS 2021), which is known as the square root law by showing that the non-asymptotic maximal number of transmitted messages has a back off that scales in the order \(\Theta(n^\frac{1}{4})\) beyond the first-order term scaling in the order \(\Theta(n^\frac{1}{2})\) when the blocklength is \(n\). Thus, our second-order asymptotic bound provides a better approximation to the finite blocklength performance of optimal codes. Furthermore, compared with the single antenna result of Yu et al. (arXiv:2305.17924v3), we demonstrate the impact of the number of antennas \(m\) and reveal spatial diversity gains of MIMO, advocating the use of MIMO for covert communication to achieve a high transmission rate. To prove our results, we extend the quasi-\(\eta\)-neighborhood framework from single-antenna real value channels to multi-antenna complex value MIMO channels. To ensure covertness, the transmission power vanishes as the blocklength \(n\) increases. Thus, we judiciously analyze the finite blocklength performance of MIMO communication by modifying critical steps concerning the Berry–Esseen Theorem to deal with vanishing second and third absolute moments of information densities that rely on blocklength, which is in stark contrast with the non-covert case.

We revisit noisy twenty questions estimation and study the privacy-resolution tradeoff for adaptive query procedures. Specifically, in twenty questions estimation, there are two players: an oracle and a questioner. The questioner aims to estimate target variables by posing queries to the oracle that knows the variables and using noisy responses to form reliable estimates. Typically, there are adaptive and non-adaptive query procedures. In adaptive querying, one designs the current query using previous queries and their noisy responses while in non-adaptive querying, all queries are posed simultaneously. Generally speaking, adaptive query procedures yield better performance. However, adaptive querying leads to privacy concerns, which were first studied by Tsitsiklis, Xu and Xu (COLT 2018) and by Xu, Xu and Yang (AISTATS 2021) for the noiseless case, where the oracle always provides correct answers to queries. In this paper, we generalize the above results to the more practical noisy case, by proposing a two-stage private query procedure, analyzing its non-asymptotic and second-order asymptotic achievable performance and discussing the impact of privacy concerns. Furthermore, when specialized to the noiseless case, our private query procedure achieves better performance than above-mentioned query procedures (COLT 2018, AISTATS 2021).

Motivated by the need for low-latency and high-throughput in the low-altitude economy scenarios with multiple hovering uncrewed aerial vehicles and a single base station, we investigate a multiple-input multiple-output (MIMO) multi-pleaccess channel (MAC) with arbitrary additive noise distribution. To characterize its finite blocklength performance, we propose mismatched coding schemes based on spherical codebooks, employing either joint nearest neighbor (JNN) or successive interference cancellation (SIC) decoders. We derive second-order asymptotics for these schemes, extending single-antenna MAC analyses to the MIMO setting and highlighting the impact of antenna number on performance. While JNN and SIC decodings yield identical first-order asymptotics, JNN decoding exhibits superior performance in low-latency communication due to a larger second-order rate region, with this performance gap increasing as the number of antennas grows.

We study the two-user broadcast channel with degraded message sets and derive second-order achievability rate regions. Specifically, the channel noises are not necessarily Gaussian and we use spherical codebooks for both users. The weak user with worse channel quality applies nearest neighbor decoding by treating the signal of the other user as interference. For the strong user with better channel quality, we consider two decoding schemes: successive interference cancellation (SIC) decoding and joint nearest neighbor (JNN) decoding. We adopt two performance criteria: separate error probabilities (SEP) and joint error probability (JEP). Under our analysis, SIC and JNN decoding share the same second-order achievable rate region despite the fact that JNN decoding often yields better performance in other multiterminal problems. Furthermore, we generalize our results to the case with quasi-static fading and show that the asymptotic notion of outage capacity region is an accurate performance measure even at finite blocklengths.

Motivated by the practical application of beam tracking of multiple devices in Multiple Input Multiple Output (MIMO) communication, we study the problem of non-adaptive twenty questions estimation for locating and tracking multiple moving targets under a query-dependent noisy channel. Specifically, we derive a non-asymptotic bound and a second-order asymptotic bound on resolution for optimal query procedures and provide numerical examples to illustrate our results. In particular, we demonstrate that the bound is achieved by a state estimator that thresholds the mutual information density over possible target locations. This single threshold decoding rule has reduced the computational complexity compared to the multiple threshold scheme proposed for locating multiple stationary targets (Zhou, Bai and Hero, TIT 2022). We discuss two special cases of our setting: the case with unknown initial location and known velocity, and the case with known initial location and unknown velocity. Both cases share the same theoretical benchmark that applies to stationary multiple target search in Zhou, Bai and Hero (TIT 2022) while the known initial location case is close to the theoretical benchmark for stationary target search when the maximal speed is inversely proportional to the number of queries. We also generalize our results to account for a piecewise constant velocity model introduced in Zhou and Hero (TIT 2023), where targets change velocity periodically. Finally, we illustrate our proposed algorithm for the application of beam tracking of multiple mobile transmitters in a 5G wireless network.

We study covert secret key generation over a two-user multiple access channel with one-way public discussion and derive bounds on the capacity region. Specifically, in this problem, there are three legitimate parties: Alice, Bob and Charlie. The goal is to allow Charlie to generate a secret key with Alice and another secret key with Bob, reliably, secretly and covertly. Reliability ensures that the key generated by Alice and Charlie is the same and the key generated by Bob and Charlie is the same. Secrecy ensures that the secret keys generated are only known to specific legitimate parties. Covertness ensures that the key generation process is undetectable by a warden Willie. As a corollary of our result, we establish bounds on the capacity region of wiretap secret key generation without the covertness constraint and discuss the impact of covertness. Our results generalize the point-to-point result of Tahmasbi and Bloch (TIFS 2020) to the setting of multiterminal communication.

Flying ad hoc networks (FANETs) offer flexible, real-time wireless communication solutions for multi-drone systems by utilizing drones as network routers. However, FANETs’ unique characteristics, including high mobility, unstable network topology, and intermittent connectivity, pose significant challenges in designing efficient and reliable routing protocols. Traditional routing protocols for mobile ad hoc networks often fall short in highly dynamic airborne environments due to excessive control overhead, increased latency, and inefficient route maintenance. To address these issues, this paper proposes an enhanced on-demand predictive (EDP) routing protocol that integrates a neighbor coverage-based predictive flooding mechanism and an adaptive link quality-based route maintenance strategy. The flooding mechanism mitigates directional deafness by using a Kalman filter-based probabilistic forwarding model, while the route maintenance method optimizes path selection based on distance, traffic load, and link lifetime. Simulation results show that EDP significantly improves packet delivery rate, reduces network delay, and lowers overhead compared to benchmarks, making it well-suited for applications in FANETs.

To satisfy diverse security requirements of ground users in unmanned aerial vehicle (UAV) networks, we propose a channel inversion power control (CIPC) aided multi-user collaborative secret and covert uplink transmission strategy for UAV secure communication. Specifically, using the non-orthogonal multiple access (NOMA) technology, multiple ground covert users named Carlo, hide their weak covert signals in the strong secret signal from a secret user named Bob, and transmit to the UAV named Alice. An adversary Willie attempts to eavesdrop Bob’s confidential message and detect whether Carlo is transmitting or not. To evaluate the link reliability and security of secret and covert transmissions, we first derive closed-form expressions of the secret connection probability (SCP), secrecy outage probability (SOP), covert connection probability (CCP), and detection error probability (DEP) under perfect channel state information while accounting for the uncertainty of the adversary’s noise power. We then further incorporate the legitimate-link channel uncertainty into the analysis and characterize its impact on the key performance metrics, particularly the average values of SCP, SOP, and CCP. To characterize the theoretical benchmark of the proposed transmission strategy, we investigate the performance in both rotary-wing and fixed-wing UAV scenarios. Particularly, in the rotary-wing UAV scenario, we formulate an optimization problem to maximize the average effective sum covert rate subject to constraints of SCP, SOP, DEP, CIPC parameter, ground user’s transmission power, and the UAV’s altitude. Subsequently, we provide an optimal and a sub-optimal solution to the optimization problem. In the fixed-wing UAV scenario, we formulate an optimization problem to maximize the average covert rate subject to the constraints of SCP, SOP, DEP, CIPC parameter, user scheduling, and the UAV’s flight parameters. Furthermore, using the successive convex approximation (SCA) method, we propose an alternating optimization (AO) algorithm to obtain a high-quality feasible solution. Finally, our results reveal the influence of key parameters on the system performance, analytically and numerically.

Due to circuit failures, defective elements that cannot adaptively adjust the phase shifts of their impinging signals in a desired manner may exist on an intelligent reflecting surface (IRS). Traditional way to locate these defective IRS elements requires a thorough diagnosis of all the circuits belonging to a huge number of IRS elements, which is practically challenging. In this paper, we will devise novel approaches under which a transmitter sends known pilot signals and a receiver localizes all the defective IRS elements just based on its over-the-air measurements reflected from the IRS. Specifically, given any set of IRS elements, we propose an efficient method to process the received signals to determine whether this cluster contains defective elements or not with a very high accuracy probability. Based on this method, we show that the over-the-air diagnosis problem belongs to the 20 questions problem, where we can adaptively change the query set at the IRS so as to localize all the defective elements as quickly as possible. Along this line, we first propose a sorted posterior matching (sortPM) based method according to the noisy 20 questions technique, which enables accurate diagnosis even if the answers about the existence of defective elements in some sets of interest are wrong at certain question and answer (Q&A) rounds due to the noisy received signals. Next, to reduce the complexity, we propose a bisection based method according to the noiseless 20 questions technique, which totally trusts the answer at each Q&A round and keeps removing half of the remaining region based on such answers. Via numerical results, we show that our proposed methods can exploit the over-the-air measurements to localize all the defective IRS elements quickly and accurately.

Motivated by the practical application of beam tracking of multiple devices in Multiple Input Multiple Output (MIMO) communication, we study the problem of non-adaptive twenty questions estimation for locating and tracking multiple moving targets under a query-dependent noisy channel. Specifically, we derive a second-order asymptotic bound on resolution for optimal query procedures and provide numerical examples to illustrate our results. In particular, we demonstrate that a single threshold decoding rule achieves the asymptotic bound. The single threshold decoding rule has reduced the computational complexity compared to the multiple threshold method proposed for locating multiple stationary targets (Zhou, Bai and Hero, TIT 2022). Finally, we illustrate our proposed algorithm for the application of beam tracking of multiple mobile transmitters in a 5G wireless network.

We study covert secret key generation over a binary-input two-user multiple access channel with one-way public discussion and derive bounds on the capacity region. Specifically, in this problem, there are three legitimate parties: Alice, Bob and Charlie. The goal is to allow Charlie to generate a secret key with Alice and another secret key with Bob, reliably, secretly and covertly. Reliability ensures that the key generated by Alice and Charlie is the same and the key generated by Bob and Charlie is the same. Secrecy ensures that the secret keys generated are only known to specific legitimate parties. Covertness ensures that the key generation process is undetectable by a warden Willie. As a corollary of our result, we establish bounds on the capacity region of wiretap secret key generation without the covertness constraint and discuss the impact of covertness. Our results generalize the point-to-point result of Tahmasbi and Bloch (TIFS 2020) to the setting of multiterminal communication.

We revisit sequential outlier hypothesis testing and derive bounds on achievable exponents when both the nominal and anomalous distributions areunknown. The task of outlier hypothesis testing is to identify the set of outliers that are generated from an anomalous distribution among all observed sequences where the rest majority are generated from a nominal distribution. In the sequential setting, one obtains a symbol from each sequence per unit time until a reliable decision could be made. For the case with exactly one outlier, our exponent bounds are tight, providing exact large deviations characterization of sequential tests and strengthening a previous result of Li, Nitinawarat and Veeravalli (2017). In particular, the average sample size of our sequential test is bounded universally under any pair of nominal and anomalous distributions and our sequential test achieves larger Bayesian exponent than the fixed-length test, which could not be guaranteed by the sequential test of Li, Nitinawarat and Veeravalli (2017). For the case with at most one outlier, we propose a threshold-based test that has bounded expected stopping time under mild conditions and we bound the exponential decay rate of error probabilities, a.k.a., error exponents, under each non-null hypothesis and the null hypothesis. Our sequential test resolves the tradeoff among the exponential decay rates of misclassification, false reject and false alarm probabilities for the fixed-length test of Zhou, Wei and Hero (TIT 2022). Finally, with a further step towards practical applications, we generalize our results to the cases of multiple outliers and show that there is a penalty in the error exponents when the number of outliers is unknown.

We first study the two-user additive noise multiple access channel (MAC) where the noise distribution is arbitrary. For such a MAC, we use spherical codebooks and either joint nearest neighbor (JNN) or successive interference cancellation (SIC) decoding. Under both decoding methods, we derive second-order achievable rate regions and compare the finite blocklength performance between JNN and SIC decoding. Our results indicate that although the first-order rate regions of JNN and SIC decoding are identical, JNN decoding has better second-order asymptotic performance. When specialized to the Gaussian noise, we provide an alternative achievability proof to the result by MolavianJazi and Laneman (T-IT, 2015). Furthermore, we generalize our results to the random access channel (RAC) where neither the transmitters nor the receiver knows the user activity pattern. We use spherical-type codebooks and a rateless transmission scheme combining JNN/SIC decoding and derive second-order achievability bounds. Comparing second-order achievability results of JNN and SIC decoding in a RAC, we show that JNN decoding achieves a strictly larger first-order asymptotic rate. When specialized to Gaussian noise, our second-order asymptotic results recover the corresponding results of Yavas, Kostina, and Effros (T-IT, 2021) up to second-order.

We study the successive refinement setting of Shannon cipher system (SCS) under the maximal leakage secrecy metric for discrete memoryless sources under bounded distortion measures. Specifically, we generalize the threat model for the point-to-point rate-distortion setting of Issa, Wagner and Kamath (T-IT 2020) to the multiterminal successive refinement setting. Under mild conditions that correspond to partial secrecy, we characterize the asymptotically optimal normalized maximal leakage region for both the joint excess-distortion probability (JEP) and the expected distortion reliability constraints. Under JEP, in the achievability part, we propose a type-based coding scheme, analyze the reliability guarantee for JEP and bound the leakage of the information source through compressed messages. In the converse part, by analyzing a guessing scheme of the eavesdropper, we prove the optimality of our achievability result. Under expected distortion, the achievability part is established similarly to the JEP counterpart. The converse proof proceeds by generalizing the corresponding results for the rate-distortion setting of SCS by Schieler and Cuff (T-IT 2014) to the successive refinement setting. Somewhat surprisingly, the normalized maximal leakage regions under both JEP and expected distortion constraints are identical under certain conditions, although JEP appears to be a stronger reliability constraint.

In outlier hypothesis testing, one aims to detect outlying sequences among a given set of sequences, where most sequences are generated i.i.d. from a nominal distribution while outlying sequences (outliers) are generated i.i.d. from a different anomalous distribution. Most existing studies focus on discrete-valued sequences, where each data sample takes values in a finite set. To account for practical scenarios where data sequences usually take real values and the number of outlying sequence is unknown, we study outlier hypothesis testing for continuous sequences when there might exist multiple outliers, and both the nominal and anomalous distributions areunknown. Specifically, we propose distribution free tests and prove that the probabilities of misclassification error, false reject and false alarm decay exponentially fast for three different test designs: fixed-length test, sequential test, and two-phase test. In a fixed-length test, one fixes the sample size of each observed sequence; in a sequential test, one takes a sample sequentially from each sequence per unit time until a reliable decision can be made; in a two-phase test, one adapts the sample size from two different fixed values. Remarkably, the two-phase test achieves a good balance between test design complexity and theoretical performance.

Motivated by diverse secure requirements of multi-user in uncrewed aerial vehicle (UAV) systems, we propose a collaborative secret and covert transmission method for multi-antenna ground users to UAV communications. Specifically, based on the power domain non-orthogonal multiple access (NOMA), two ground users with distinct security requirements, named Bob and Carlo, superimpose their signals and transmit the combined signal to the UAV named Alice. An adversary Willie attempts to simultaneously eavesdrop Bob’s confidential message and detect whether Carlo is transmitting or not. We derive close-form expressions of the secrecy connection probability (SCP) and the covert connection probability (CCP) to evaluate the link reliability for wiretap and covert transmissions, respectively. Furthermore, we bound the secrecy outage probability (SOP) from Bob to Alice and the detection error probability (DEP) of Willie to evaluate the link security for wiretap and covert transmissions, respectively. To characterize the theoretical benchmark of the above model, we formulate a weighted multi-objective optimization problem to maximize the average of secret and covert transmission rates subject to constraints SOP, DEP, the beamformers of Bob and Carlo, and UAV trajectory parameters. To solve the optimization problem, we propose an iterative optimization algorithm using successive convex approximation and block coordinate descent (SCA-BCD) methods. Our results reveal the influence of design parameters of the system on the wiretap and covert rates, analytically and numerically. In summary, our study fills the gaps in collaborative secret and covert transmission for multi-user multi-antenna uplink UAV communications and provides insights to construct such systems.

We revisit the problem of statistical sequence matching between two databases of sequences initiated by Unnikrishnan (TIT 2015) and derive achievable theoretical performance guar-antees for a generalized likelihood ratio test (G LRT) in the large deviations regime, when the number of matched pairs of sequences between two databases is unknown. In this case, the task is to accurately estimate the number of matched pairs and identify the matched pairs of sequences among all possible matches between the sequences in the two databases. We generalize the GLRT by Unnikrishnan and explicitly characterize the tradeoff among the exponential decay rates for probabilities of mismatch, false reject and false alarm. When one of the two databases contains a single sequence, the problem of statistical sequence matching specializes to the problem of multiple classification introduced by Gutman (TIT 1989). For this special case, our result strengthens previous result of Gutman (TIT 1989) and Zhou, Tan and Motani (Information and Inference 2020) by allowing the testing sequence to be generated from a distribution that is different from generating distributions of all training sequences.

We revisit sequential outlier hypothesis testing and derive bounds on the achievable exponents. Specifically, the task of outlier hypothesis testing is to identify the set of outliers that are generated from an anomalous distribution among all observed sequences where most are generated from a nominal distribution. In the sequential setting, one obtains a sample from each sequence per unit time until a reliable decision could be made. We assume that the number of outliers is known while both the nominal and anomalous distributions are unknown. For the case of exactly one outlier, our bounds on the achievable exponents are tight, providing exact large deviations characterization of sequential tests and strengthening a previous result of Li, Nitinawarat and Veeravalli (2017). In particular, we propose a sequential test that has bounded average sample size and better theoretical performance than the fixed-length test, which could not be guaranteed by the corresponding sequential test of Li, Nitinawarat and Veeravalli (2017). Our results are also generalized to the case of multiple outliers.

The task of outlier hypothesis testing is to identify outliers from a set of observed sequences, where most sequences named nominal samples are generated from nominal distributions and the rest sequences called outliers are generated from anomalous distributions. Inspired by the study of binary classification with distribution mismatch by Hsu and Wang (ISIT 2020), we study outlier hypothesis testing with distribution uncertainty. Specifically, each nominal sequence is generated from a distribution close to a centered nominal distribution and each outlier is generated from a distribution close to a centered anomalous distribution, where the closeness is measured via L-norms. Both nominal and anomalous distributions are unknown. To solve the above problem, we propose a threshold-based test and characterize the performance of our test in both the Chernoff's and Stein's regimes. Furthermore, in the Stein's regime, we analyze the impact of distribution uncertainty on the asymptotic performance of our result and show that the dominant term is a function of the likelihood ratio between centered nominal and anomalous distributions.

In outlier hypothesis testing, one aims to detect outlying sequences among a given set of sequences, where most sequences are generated i.i.d. from a nominal distribution while outlying sequences (outliers) are generated i.i.d. from a different anomalous distribution. Most existing studies focus on discrete-valued sequences, where each data sample takes values in a finite set. To account for practical scenarios where data sequences usually take real values, we study outlier hypothesis testing for continuous sequences when both the nominal and anomalous distributions are unknown. Specifically, we propose distribution free test and prove that the probabilities of misclassification error, false reject and false alarm decay exponentially fast for the proposed test, where one fixes the sample size of each observed sequence. In this work, we mainly consider the case with multiple but unknown number of outliers.

We revisit the problem of statistical sequence matching between two databases of sequences initiated by Unnikrishnan, (2015) and derive theoretical performance guarantees for the generalized likelihood ratio test (GLRT). We first consider the case where the number of matched pairs of sequences between the databases is known. In this case, the task is to accurately find the matched pairs of sequences among all possible matches between the sequences in the two databases. We analyze the performance of the GLRT by Unnikrishnan and explicitly characterize the tradeoff between the mismatch and false reject probabilities under each hypothesis in both large and small deviations regimes. Furthermore, we demonstrate the optimality of Unnikrishnan’s GLRT test under the generalized Neyman-Person criterion for both regimes and illustrate our theoretical results via numerical examples. Subsequently, we generalize our achievability analyses to the case where the number of matched pairs is unknown, and an additional error probability needs to be considered. When one of the two databases contains a single sequence, the problem of statistical sequence matching specializes to the problem of multiple classification introduced by Gutman, (1989). For this special case, our result for the small deviations regime strengthens previous result of Zhou et al., (2020) by removing unnecessary conditions on the generating distributions.

We derive a second-order achievability bound for the two-user multiple access channel with additive non-Gaussian noise. In our setting, both users use spherical codebooks and the decoder uses the nearest neighbor decoding. Our result generalizes the dispersion analysis for point-to-point mismatched channel coding by Scarlett, Tan and Durisi (TIT 2017) to the multiple user setting. When specialized to the Gaussian noise, our proof provides an alternative second-order achievability analysis of MolavianJazi and Laneman (TIT, 2015). Furthermore, we generalize our results to the random access channel with additive non-Gaussian noise, where the number of active users in each time slot are unknown, and derive a second-order achievability bound. When specialized to the Gaussian noise, our second-order asymptotic results are consistent with the Gaussian noise case recently derived by Yavas, Kostina and Effros (TIT, 2021).

We revisit multiple hypothesis testing and propose a two-phase test, where each phase is a fixed-length test and the second-phase proceeds only if a reject option is decided in the first phase. We derive achievable error exponents of error probabilities under each hypothesis and show that our two-phase test bridges over fixed-length and sequential tests in both Neyman-Pearson and Bayesian settings in the similar spirit of Lalitha and Javidi [1] for binary hypothesis testing. Specifically, our test may achieve the performance close to a sequential test with the asymptotic complexity of a fixed-length test and such test is named the almost fixed-length test. Our results generalize the design and analysis of the almost fixed-length test for binary hypothesis testing to account for more than two outcomes.

We revisit the multiple classification problem and propose a two-phase test, where each phase is a fixed-length test and the second-phase proceeds only if a reject option is decided in the first phase. We derive the achievable error exponent under each hypothesis and show that our two-phase test bridges over the fixed-length test of Gutman (TIT, 1989) and the sequential test of Haghifam, Tan, and Khisti (TIT 2021). In contrast to the fixed-length test of Gutman that requires an additional reject option, with proper choices of test parameters, our test achieves error exponents close to the sequential test of Haghifam, Tan, and Khisti without a reject option. We generalize the result of Lalitha and Javidi (ISIT 2016) for binary hypothesis testing to the more practical families of M-ary statistical classification, where the test outcome is more than two and the generating distribution under each hypothesis is unknown.

We study the problem of adaptive search for multiple targets using the framework of 20 questions estimation under the query-dependent noise channel. Specifically, we propose an adaptive query strategy that combines the ideas of non-adaptive search for multiple targets using random coding by Zhou, Bai and Hero (TIT, 2022) and adaptive search for one target using variable-length coding with feedback by Zhou and Hero (ISIT, 2021). Our main contribution is the derivation of the non-asymptotic and second-order asymptotic performance of our adaptive query procedure. Furthermore, we discuss the benefit of adaptivity, analytically and numerically, by comparing our results with the non-adaptive counterparts.

We study the successive refinement problem of Shannon cipher system under maximal leakage for a discrete memoryless source with arbitrary bounded distortion measures. Specifically, we generalize the threat model described by Issa, Wagner and Kamath (T-IT, 2020) to the successive refinement setting and derive the optimal asymptotic normalized maximal leakage region under a joint excess-distortion probability constraint. In the achievability part, we propose a type-based coding scheme and derive the asymptotic achievable normalized maximal leakage region. In the converse part, by analyzing the guessing scheme of the eavesdropper, we manage to show the above normalized maximal leakage region is optimal. Our results reveal the fundamental tradeoff between reliability and secrecy. Furthermore, for a successively refinable source-distortion measure triplet, we find that our coding scheme satisfies the successive refinability under the maximal leakage metric.

Covert communication, also known as communication with low probability of detection, aims to provide reliable communication for legal users and prevent any other user from detecting the occurrence of legal communication. Motivated by the strong need of security links of the next generation communication systems, we study covert communication with millimeter-wave (mmWave) massive multiple-input multiple-output (MIMO) hybrid beamforming. Consistent with existing studies on covert communication, we use the Kullback-Leibler (KL) divergence and the total variation (TV) distance as the covertness measure. Under both covertness measures, for block fading channels, we derive the covert transmission rate with and without artificial noise. These results are obtained by optimizing the transmit power and the jamming power to satisfy the covertness constraints and to maximize the transmission rate. Specifically, when artificial noise is allowed, we show that there exists an optimal jamming power to achieve the covert transmission rate given the transmit signal power. Furthermore, we propose a metric to measure the inherent sparsity of the mmWave massive MIMO channel in the spatial domain, and study its effect on the covertness measures and the corresponding covert transmission rates. Our results provide insights and benchmarks for the design of practical covert communication systems with mmWave massive MIMO.

We study the mismatched successive refinement problem where one uses Gaussian codebooks to compress an arbitrary memoryless source with successive minimum Euclidean distance encoding under the quadratic distortion measure. Specifically, we derive achievable refined asymptotics under both the joint excess-distortion probability (JEP) and the separate excess-distortion probabilities (SEP) criteria. For both second-order and moderate deviations asymptotics, we consider two types of codebooks: the spherical codebook where each codeword is drawn independently and uniformly from the surface of a sphere and the i.i.d. Gaussian codebook where each component of each codeword is drawn independently from a Gaussian distribution. We establish the achievable second-order rate-region under JEP and we show that under SEP any memoryless source satisfying mild moment conditions is strongly successively refinable. When specialized to a Gaussian memoryless source (GMS), our results provide an alternative achievability proof with specific code design. We show that under JEP and SEP, the same moderate deviations constant is achievable. For large deviations asymptotics, we only consider the i.i.d. Gaussian codebook since the i.i.d. Gaussian codebook has better performance than the spherical codebook in this regime for the one layer mismatched rate-distortion problem (Zhou et al., 2019). We derive achievable exponents of both JEP and SEP and specialize our results to a GMS, which appears to be a novel result of independent interest.

Using the 20 questions estimation framework with query-dependent noise, we study non-adaptive search strategies for a moving target over the unit cube with unknown initial location and velocities under a piecewise constant velocity model. In this search problem, there is an oracle who knows the instantaneous location of the target at any time. Our task is to query the oracle as few times as possible to accurately estimate the location of the target at any specified time. We first study the case where the oracle’s answer to each query is corrupted by discrete noise and then generalize our results to the case of additive white Gaussian noise. In our formulation, the performance criterion is the resolution, which is defined as the maximal$L_{\infty} $distance between the true locations and estimated locations. We characterize the minimal resolution of an optimal non-adaptive query procedure with a finite number of queries by deriving non-asymptotic and asymptotic bounds. Our bounds are tight in the first-order asymptotic sense when the number of queries satisfies a certain condition and our bounds are tight in the stronger second-order asymptotic sense when the target moves with a constant velocity. To prove our results, we relate the current problem to channel coding, borrow ideas from finite blocklength information theory and construct bounds on the number of possible quantized target trajectories.

Due to increasing demands of seamless connection and massive information exchange across the world, the integrated satellite-terrestrial communication systems develop rapidly. To shed lights on the design of this system, we consider an uplink communication model consisting of a single satellite, a single terrestrial station and multiple ground users. The terrestrial station uses decode-and-forward (DF) to facilitate the communication between ground users and the satellite. The channel between the satellite and the terrestrial station is assumed to be a quasi-static shadowed Rician fading channel, while the channels between the terrestrial station and ground users are assumed to experience independent quasi-static Rayleigh fading. We consider two cases of channel state information (CSI) availability. When perfect CSI is available, we derive the instantaneous achievable sum rate of all ground users and formulate an optimization problem to maximize the sum rate. When only channel distribution information (CDI) is available, we derive a closed-form expression for the outage probability and formulate another optimization problem to minimize the outage probability. Both optimization problems correspond to scheduling algorithms for ground users. For both cases, we propose low-complexity user scheduling algorithms and demonstrate the efficiency of our scheduling algorithms via numerical simulations.

We revisit the binary classification problem where the generating distribution under each hypothesis is unknown and propose a two-phase test, where each phase is a fixed-length test and the second-phase proceeds only if a reject option is decided in the first phase. We derive the achievable error exponents of both type-I and type-II error probabilities. Furthermore, we illustrate our results via numerical examples and show that the performance close to sequential test can be achieved with the much simpler and less complex almost fixed-length test. Our results generalize the design and analysis of the almost fixed-length test for binary hypothesis testing (Lalitha and Javidi, ISIT 2016) to the more practical setting of binary classification.

This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We derive achievability results on large deviations for mismatched successive refinement where one uses random i.i.d. Gaussian codebooks and minimum Euclidean distance encoding to compress an arbitrary memoryless source. Specifically, we consider both separate and joint excess-distortion criterion and derive achievable error exponents for both cases. Under the mismatched coding scheme, we show that the exponent of the joint excess-distortion probability equals the exponent of one of the separate excess-distortion probabilities, depending on the compression rate of the second encoder only. When specialized to a Gaussian memoryless source (GMS), we obtain the first achievable error exponent region. However, in contrast to the second-order asymptotics and to the large deviations for mismatched rate-distortion, the specialized result for GMS is not optimal. Further investigations are required to close the gap.

We revisit the outlier hypothesis testing framework of Li et al. (TIT 2014) and derive fundamental limits for the optimal test under the generalized Neyman-Pearson criterion. In outlier hypothesis testing, one is given multiple observed sequences, where most sequences are generated i.i.d. from a nominal distribution. The task is to discern the set of outlying sequences that are generated according to anomalous distributions. The nominal and anomalous distributions are unknown. We consider the case of multiple outlying sequences where the number of outlying sequences is unknown and each outlying sequence can follow a different anomalous distribution. Under this setting, we study the tradeoff among the probabilities of misclassification error, false alarm and false reject. Specifically, we propose a threshold-based test that ensures exponential decay of misclassification error and false alarm probabilities. We study two constraints on the false reject probability, with one constraint being that it is a non-vanishing constant and the other being that it has an exponential decay rate. For both cases, we derive bounds on the false reject probability, as a function of the threshold, for each tuple of nominal and anomalous distributions.

We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive fundamental resolution limits of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal$L_\infty $norm between the location vector and its estimated version where the maximization is over all target location vectors. The fundamental resolution limit is defined as the minimal achievable resolution of any non-adaptive query procedure, where each query has binary yes/no answers. We drive non-asymptotic and second-order asymptotic bounds on the minimal achievable resolution, using tools from finite blocklength information theory. Specifically, in the achievability part, we relate the 20 questions problem to data transmission over a multiple access channel, use the information spectrum method by Han and borrow results from finite blocklength analysis for random access channel coding. In the converse part, we relate the 20 questions problem to data transmission over a point-to-point channel and adapt finite blocklength converse results for channel coding. Our results extend the purely first-order asymptotic analyses of Kaspiet al.(ISIT 2015) for the one-dimensional case: we consider channels beyond the binary symmetric channel and derive non-asymptotic and second-order asymptotic bounds on the performance of optimal non-adaptive query procedures.

We revisit the outlier hypothesis testing framework of Liet al.(TIT 2014) and derive fundamental limits for the optimal test under the generalized Neyman-Pearson criterion. In outlier hypothesis testing, one is given multiple observed sequences, where most sequences are generated i.i.d. from a nominal distribution. The task is to discern the set of outlying sequences that are generated from anomalous distributions. The nominal and anomalous distributions areunknown. We study the tradeoff among the probabilities of misclassification error, false alarm and false reject for tests that satisfy weak conditions on the rate of decrease of these error probabilities as a function of sequence length. Specifically, we propose a threshold-based test that ensures exponential decay of misclassification error and false alarm probabilities. We study two constraints on the false reject probability, with one constraint being that it is a non-vanishing constant and the other being that it has an exponential decay rate. For both cases, we characterize bounds on the false reject probability, as a function of the threshold, for each pair of nominal and anomalous distributions and demonstrate the optimality of our test under the generalized Neyman-Pearson criterion. We first consider the case of at most one outlying sequence and then generalize our results to the case of multiple outlying sequences where the number of outlying sequences is unknown and each outlying sequence can follow a different anomalous distribution.

We establish fundamental limits of tracking a moving target over the unit cube under the framework of 20 questions with measurement-dependent noise. In this problem, there is an oracle who knows the instantaneous location of a target. Our task is to query the oracle as few times as possible to accurately estimate the trajectory of the moving target, whose initial location and velocity is unknown. We study the case where the oracle’s answer to each query is corrupted by random noise with query-dependent discrete distribution. In our formulation, the performance criterion is the resolution, which is defined as the maximal absolute value between the true location and estimated location at each discrete time during the searching process. We are interested in the minimal resolution of any non-adaptive searching procedure with a finite number of queries and derive approximations to this optimal resolution via the second-order asymptotic analysis.

We study the mismatched successive refinement problem where one uses a fixed code to compress an arbitrary source with random Gaussian codebooks and minimum Euclidean distance encoding in a successive manner. Specifically, we generalize the mismatched rate-distortion framework by Lapidoth (T-IT, 1997) to the successive refinement setting and derive the achievable second-order asymptotics. Our result implies that any source that satisfies a mild moment constraint is successive refinable under our code. Furthermore, our proof, when specialized to a Gaussian memoryless source, provides an alternative achievability proof with structured codebooks for the successive refinement problem, which was studied by Zhou, Tan, Motani (T-IT, 2018) where a covering lemma without specifying the locations of codewords was used.

We study the achievable performance of adaptive query procedures for the noisy 20 questions problem with measurement-dependent noise over a unit cube of finite dimension. The performance criterion that we consider is the minimal resolution, defined as the$L$∞norm between the estimated and the true values of the random location vector of a target, given a finite number of queries constrained by an excess-resolution probability. Specifically, we derive the achievable resolution of an adaptive query procedure based on the variable length feedback code by Polyanskiy et al. (TIT 2011). Furthermore, we verify our theoretical results with numerical simulations and compare the performance of our considered adaptive query procedure with that of certain state-of-the-art algorithms, such as the sorted posterior matching algorithm by Chiu and Javadi (ITW 2016). In particular, we demonstrate that the termination strategy adopted in our adaptive query procedure can significantly enhance the asymptotic performance of adaptive query procedures, especially at moderate to large excess-resolution probability constraints.

We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive the fundamental resolution limit of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal$L$∞norm between the location vector and its estimated version where the maximization is over the possible location vectors of all targets. The fundamental resolution limit is then defined as the minimal achievable resolution of any nonadaptive query procedure. We drive the second-order asymptotic bound on the minimal achievable resolution by relating the current problem to a data transmission problem over a multiple access channel, using the information spectrum by Han and borrowing results from finite blocklength information theory for random access channel coding. Our results extend the purely first-order asymptotic analyses of Kaspi et al. (ISIT 2015) for the one-dimensional case. Specifically, we consider more general channels, derive the second-order asymptotic result and establish a phase transition phenomenon.

Motivated by practical machine learning applications, we revisit the outlying sequence detection problem (Li et al., TIT 2014) and derive fundamental limits of optimal detection when the reject option is allowed for outlying sequences. In the considered outlying sequence detection (OSD) problem, one is given multiple observed sequences, where all sequences are generated i.i.d. from a nominal distribution with at most one exception. The task is to discern the outlying sequence that is generated according to an anomalous distribution. In OSD, the nominal and anomalous distributions are unknown. In this paper, we consider the case where there is a reject option for the OSD, i.e., we reject the samples as insufficient for making a reliable decision (cf. Bartlett et al., JMLR 2008). We study the tradeoff among the probabilities of misclassification error, false alarm and false reject for tests that satisfy weak conditions on the rate of decrease of these error probabilities as a function of sequence length. We propose a second-order asymptotically optimal test that provides a finite sample approximation to the error probabilities.

We study a hypothesis testing problem with a privacy constraint over a noisy channel and derive the performance of optimal tests under the Neyman-Pearson criterion. The fundamental limit of interest is the privacy-utility tradeoff (PUT) between the exponent of the type-II error probability and the leakage of the information source subject to a constant constraint on the type-I error probability. We provide an exact characterization of the asymptotic PUT for any non-vanishing type-I error probability. Our result implies that tolerating a larger type-I error probability cannot improve the PUT. Such a result is known as a strong converse or strong impossibility theorem. To prove the strong converse theorem, we apply the recently proposed technique in (Tyagi and Watanabe, 2020) and further demonstrate its generality. The strong converse theorems for several problems, such as hypothesis testing against independence over a noisy channel (Sreekumar and Gündüz, 2020) and hypothesis testing with communication and privacy constraints (Gilani et al., 2020), are established or recovered as special cases of our result.

We establish fundamental limits on estimation accuracy for the noisy 20 questions problem with measurement-dependent noise and introduce optimal non-adaptive procedures that achieve these limits. The minimal achievable resolution is defined as the absolute difference between the estimated and the true locations of a target over a unit cube, given a finite number of queries constrained by the excess-resolution probability. Inspired by the relationship between the 20 questions problem and the channel coding problem, we derive non-asymptotic bounds on the minimal achievable resolution to estimate the target location. Furthermore, applying the Berry-Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint. We specialize our second-order results to measurement-dependent versions of several channel models including the binary symmetric, the binary erasure and the binary Z- channels. As a complement, we establish a second-order asymptotic achievability bound for adaptive querying and use this to bound the benefit of adaptive querying.

We study fundamental limits of estimation accuracy for the noisy 20 questions problem with measurement-dependent noise and introduce optimal non-adaptive procedures that achieve these limits. The minimal achievable resolution is defined as the absolute difference between the estimated and the true values of the target random variable, given a finite number of queries constrained by the excess-resolution probability. Inspired by the relationship between the 20 questions problem and the channel coding problem, we derive non-asymptotic bounds on the minimal achievable resolution. Furthermore, applying the Berry-Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to finite blocklength performance, specifically the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint.

We propose a method to study the secrecy constraints in key generation problems where side information might be present at untrusted users. Our method is inspired by a recent work of Hayashi and Tan who used the Rényi divergence as the secrecy measure to study the output statistics of applying hash functions to a random sequence. By generalizing the achievability result of Hayashi and Tan to the multi-terminal case, we obtain the output statistics of applying hash functions to multiple random sequences, which turn out to be an important tool in the achievability proof of strong secrecy capacity regions of key generation problems with side information at untrusted users. To illustrate the power of our method, we derive the capacity region of the multiple private key generation problem with an untrusted helper for continuous memoryless sources under Markov conditions. The converse proof of our result follows by generalizing a result of Nitinawarat and Narayan to the case with side information at untrusted users.

Consider a distributed detection problem in which the underlying distributions of the observations are unknown; instead of these distributions, noisy versions of empirically observed statistics are available to the fusion center. These empirically observed statistics, together with source (test) sequences, are transmitted through different channels to the fusion center. The fusion center decides which distribution the source sequence is sampled from based on these data. For the binary case, we derive the optimal type-II error exponent given that the type-I error decays exponentially fast. The type-II error exponent is maximized over the proportions of channels for both source and training sequences. We conclude that as the ratio of the lengths of training to test sequences α tends to infinity, using only one channel is optimal. By calculating the derived exponents numerically, we conjecture that the same is true when α is finite under certain conditions. We relate our results to the classical distributed detection problem studied by Tsitsiklis, in which the underlying distributions are known. Finally, our results are extended to the case of m-ary distributed detection with a rejection option.

We revisit the successive refinement problem with causal decoder side information considered by Maor and Merhav (2008) and strengthen their result by deriving an exponential strong converse theorem. To be specific, we show that for any rate-distortion tuple outside the rate-distortion region of the successive refinement problem with causal decoder side information, the excess-distortion probability approaches one exponentially fast. Our proof follows by judiciously adapting the recently proposed strong converse technique by Oohama using the information spectrum method, the variational form of the rate-distortion region and Hölder's inequality. The lossy source coding problem with causal decoder side information considered by El Gamal and Weissman is a special case of the current problem. Therefore, the exponential strong converse theorem for the El Gamal and Weissman problem follows as a corollary of our result.

Motivated by real-world machine learning applications, we analyze approximations to the non-asymptotic fundamental limits of statistical classification. In the binary version of this problem, given two training sequences generated according to two unknown distributions P1and P2, one is tasked to classify a test sequence which is known to be generated according to either P1or P2. This problem can be thought of as an analogue of the binary hypothesis testing problem but in the present setting, the generating distributions are unknown. Due to finite sample considerations, we consider the second-order asymptotics (or dispersion-type) tradeoff between type-I and type-II error probabilities for tests which ensure that (i) the type-I error probability for all pairs of distributions decays exponentially fast and (ii) the type-II error probability for a particular pair of distributions is non-vanishing. We generalize our results to classification of multiple hypotheses with the rejection option.

By proving a strong converse, we strengthen the weak converse result by Salehkalaibar, Wigger and Wang (2017) concerning hypothesis testing against independence over a two-hop network with communication constraints. Our proof follows by judiciously combining two recently proposed techniques for proving strong converse theorems, namely the strong converse technique via reverse hypercontractivity by Liu, van Handel, and Verdú (2017) and the strong converse technique by Tyagi and Watanabe (2018), in which the authors used a change-of-measure technique and replaced hard Markov constraints with soft information costs. The techniques used in our paper can also be applied to prove strong converse theorems for other multiterminal hypothesis testing against independence problems.

We consider a binary distributed detection problem in which the distributions of the sensor observations are unknown and only empirically observed statistics are available to the fusion center. The source (test) sequences are transmitted through different channels to the fusion center, which also observes noisy versions of labelled training sequences generated independently from the two underlying distributions. The fusion center decides which distribution the source sequence is sampled from based on the observed statistics, i.e., the noisy training data. We derive the optimal type-II error exponent given that the type-I error decays exponentially fast. We further maximize the type-II error exponent over the proportions of channels for both source and training sequences and conclude that as the ratio of the lengths of training to test sequences tends to infinity, using only one channel is optimal. Finally, we relate our results to the distributed detection problem studied by Tsitsiklis.

We consider the lossy transmission of a single source over parallel additive white Gaussian noise channels with independent quasi-static fading, which we term the lossy multi-connectivity problem. We assume that only the decoder has access to the channel state information. Motivated by ultra-reliable and low latency communication requirements, we are interested in the finite blocklength performance of the problem, i.e., the minimal excess-distortion probability of transmitting k source symbols over n channel uses. By generalizing non-asymptotic bounds by Kostina and Verdú for the lossy joint source-channel coding problem, we derive non-asymptotic achievability and converse bounds for the lossy multi-connectivity problem. Using these non-asymptotic bounds and under mild conditions on the fading distribution, we derive approximations for the finite blocklength performance in the spirit of second-order asymptotics for any discrete memoryless source under an arbitrary bounded distortion measure. Furthermore, in the achievability part, we analyze the performance of a universal coding scheme by modifying the universal joint source-channel coding scheme by Csiszár and using a generalized minimum distance decoder. Our results demonstrate that the asymptotic notions of outage probability and outage capacity are in fact reasonable criteria even in the finite blocklength regime. Finally, we illustrate our results via numerical examples.

In this paper, we revisit two multi-terminal lossy source coding problems: the lossy source coding problem with side information available at the encoder and one of the two decoders, which we term as the Kaspi problem (Kaspi, 1994), and the multiple description coding problem with one semi-deterministic distortion measure, which we refer to as the Fu-Yeung problem (Fu and Yeung, 2002). For the Kaspi problem, we first present the properties of optimal test channels. Subsequently, we generalize the notion of the distortion-tilted information density for the lossy source coding problem to the Kaspi problem and prove a non-asymptotic converse bound using the properties of optimal test channels and the well-defined distortion-tilted information density. Finally, for discrete memoryless sources, we derive refined asymptotics which includes the second-order, large, and moderate deviations asymptotics. In the converse proof of second-order asymptotics, we apply the Berry-Esseen theorem to the derived non-asymptotic converse bound. The achievability proof follows by first proving a type-covering lemma tailored to the Kaspi problem, then properly Taylor expanding the well-defined distortion-tilted information densities and finally applying the Berry-Esseen theorem. We then generalize the methods used in the Kaspi problem to the Fu-Yeung problem. As a result, we obtain the properties of optimal test channels for the minimum sum-rate function, a non-asymptotic converse bound and refined asymptotics for discrete memoryless sources. Since the successive refinement problem is a special case of the Fu-Yeung problem, as a by-product, we obtain a non-asymptotic converse bound for the successive refinement problem, which is a strict generalization of the non-asymptotic converse bound for successively refinable sources (Zhou, Tan, and Motani, 2017).

We consider a joint source channel coding (JSCC) problem in which we desire to transmit an arbitrary memoryless source over an arbitrary additive channel. We propose a mismatched coding architecture that consists of Gaussian codebooks for both the source reproduction sequences and channel codewords. The natural nearest neighbor encoder and decoder, however, need to be judiciously modified to obtain the highest communication rates at finite blocklength. In particular, we consider an unequal error protection scheme in which all sources are partitioned into disjoint power-type classes. We also regularize the nearest neighbor decoder so that an appropriate measure of the size of each power type class is taken into account in the decoding strategy. For such an architecture, we derive ensemble-tight second-order and moderate deviations results. Our first-order (optimal bandwidth expansion ratio) result generalizes the seminal results by Lapidoth (1996 and 1997). The dispersion of our JSCC scheme is a linear combination of the mismatched dispersions for the channel coding saddle-point problem by Scarlett, Tan, and Durisi (2017) and the rate-distortion saddle-point problem by the present authors, thus also generalizing these results.

The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth's analysis in several directions in this paper. First, we consider refined asymptotics. In particular, when the source is stationary and memoryless, we establish the second-order, moderate, and large deviation asymptotics of the problem. Second, by random Gaussian codebook, Lapidoth referred to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an n -dimensional sphere. To be more precise, we term this as a spherical codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We derive the second-order, moderate, and large deviation asymptotics when i.i.d. Gaussian codebooks are employed. In contrast to the recent work on the channel coding counterpart by Scarlett, Tan, and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian codebooks are identical. The ensemble excess-distortion exponents for both spherical and i.i.d. Gaussian codebooks are established for all rates. Furthermore, we show that the i.i.d. Gaussian codebook has a strictly larger excess-distortion exponent than its spherical counterpart for any rate greater than the ensemble rate-distortion function derived by Lapidoth.

In this paper, we are interested in the lossy transmission of a single source over parallel additive white Gaussian noise channels with independent quasi-static fading and receiver channel state information. We call this the lossy multi-connectivity problem. Motivated by the ultra-reliable and low latency communication requirements, we consider the finite blocklength performance of lossy multi-connectivity. By generalizing the non-asymptotic bounds of Kostina and Verdti for the lossy joint source-channel coding problem, we derive nonasymptotic achievability and converse bounds for the lossy multi-connectivity problem. Using these non-asymptotic bounds, under mild conditions on the fading distribution, we derive good approximations for the finite blocklength performance in the spirit of second-order asymptotics for any discrete memoryless source under any bounded distortion measure. Our results demonstrate that the asymptotic notions of outage probability and outage capacity are actually good criteria even in the finite blocklength regime. Finally, we illustrate our results via numerical examples.

The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth's analysis in several directions in this paper. Firstly, we consider second-order asymptotics. In particular, when the source is stationary and memoryless, we establish ensemble tight second-order coding rate for the problem. Secondly, by “random Gaussian codebook”, Lapidoth refers to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an n-dimensional sphere. To be more precise, we term this as a spherical Gaussian codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We also derive the second-order asymptotics when i.i.d. Gaussian codebooks are employed. Interestingly, in contrast to the recent work on the channel coding counterpart by Scarlett, Tan and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian code books are identical for the rate-distortion saddle-point problem.

We consider a universal joint source channel coding (JSCC) scheme to transmit an arbitrary memoryless source over an arbitrary additive channel. We adopt an architecture that consists of Gaussian codebooks for both the source reproduction sequences and channel codewords. The natural minimum Euclidean distance encoder and decoder, however, need to be judiciously modified to ensure universality as well as to obtain the best (highest) possible communication rates. In particular, we consider the analogue of an unequal error (or message) protection scheme in which all sources are partitioned into disjoint power type classes. We also regularize the nearest neighbor decoder so an appropriate measure of the size of each power type class is taken into account in the decoding strategy. For such an architecture, we derive ensemble tight second-order asymptotics.

Motivated by streaming multi-view video coding and wireless sensor networks, we consider the problem of blockwise streaming compression of a pair of correlated sources, which we term streaming Slepian-Wolf coding. We study the moderate deviations regime in which the rate pairs of a sequence of codes converge, along a straight line, to various points on the boundary of the Slepian-Wolf region at a speed slower than the inverse square root of the blocklength n, while the error probability decays subexponentially fast in n. Our main result focuses on the directions of approaches to corner points of the Slepian-Wolf region. It states that for each correlated source and all corner points, there exists a non-empty subset of directions of approaches, such that the moderate deviations constant (the constant of proportionality for the subexponential decay of the error probability) is enhanced (over the non-streaming case) by at least a factor of T, the block delay of decoding source block pairs. We specialize our main result to the setting of streaming lossless source coding and generalize this result to the setting, where we have different delay requirements for each of the two source blocks. The proof of our main result involves the use of various analytical tools and amalgamates several ideas from the recent information-theoretic streaming literature. We adapt the so-called truncated memory encoding idea from Draper and Khisti (2011) and Lee, Tan, and Khisti (2016) to ensure that the effect of error accumulation is nullified in the limit of large block lengths. We also adapt the use of the so-called minimum weighted empirical suffix entropy decoder, which was used by Draper, Chang, and Sahai (2014) to derive achievable error exponents for symbolwise streaming Slepian-Wolf coding.

We revisit the high-dimensional content identification with lossy recovery problem (Tuncel and Gündüz, 2014) and establish an exponential strong converse theorem. As a corollary of the exponential strong converse theorem, we derive an upper bound on the joint identification-error and excess-distortion exponent for the problem. Our main results can be specialized to the biometrical identification problem (Willems, 2003) and the content identification problem (Tuncel, 2009) since these two problems are both special cases of the content identification with lossy recovery problem. We leverage the information spectrum method introduced by Oohama and adapt the strong converse techniques therein to be applicable to the problem at hand.

In this paper, we revisit the lossy source coding problem with side information available at the encoder and one of the two decoders, which we term as the Kaspi problem (Kaspi, 1994). For the Kaspi problem, we first present the properties of optimal test channels for the rate-distortion function. Subsequently, we generalize the notion of distortion-tilted information density for the lossy source coding problem to the Kaspi problem and prove a non-asymptotic converse bound using the properties of optimal test channels and the well- defined distortion-tilted information density. Finally, we derive the exact second-order coding rate of the Kaspi problem for discrete memoryless sources.

In this paper, we revisit the multiple description coding problem with one semi-deterministic distortion measure, which we term as the Fu- Yeung problem (Fu and Yeung, 2002). We present the properties of optimal test channels for the minimum sum-rate function, a non- asymptotic converse bound and second-order asymptotics for discrete memoryless sources. Since the successive refinement problem is a special case of the Fu-Yeung problem, as a by-product, we obtain a non-asymptotic converse bound for the successive refinement problem, which turns out to be a strict generalization of the non-asymptotic converse bound for successively refinable sources (Zhou, Tan and Motani, 2017).

In this paper, we revisit the content identification problem with lossy recovery (Tuncel and Gündüz, 2014) and establish the exponential strong converse theorem for the problem. Further, we derive an upper bound on the joint excess-distortion and error exponent for the problem.

Motivated by streaming multi-view video coding, we consider the problem of blockwise streaming compression of a pair of correlated sources, which we term streaming Slepian-Wolf coding. We study the moderate deviations regime in which the rate pairs of a sequence of codes converges, along a straight line, to various points on the boundary of the Slepian-Wolf region at a speed slower than the inverse square root of the blocklength n, while the error probability decays subexponentially fast in n. Our main result focuses on directions of approaches to corner points of the Slepian-Wolf region. It states that for each correlated source and all corner points, there exists a non-empty subset of directions of approaches such that the moderate deviations constant (the constant of proportionality for the subexponential decay of the error probability) is enhanced (over the non-streaming case) by at least a factor of T, the block delay of decoding symbol pairs. Further, we specialize our main result to the setting of lossless streaming source coding.

In this paper, we revisit the discrete lossy Gray-Wyner problem. In particular, we derive its optimal second-order coding rate region, its error exponent (reliability function), and its moderate deviations constant under mild conditions on the source. To obtain the second-order asymptotics, we extend some ideas from Watanabe's work. In particular, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú. The converse part uses a perturbation argument by Gu and Effros in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses two novel elements: 1) a generalization of various type covering lemmas and 2) the uniform continuity of the conditional rate-distortion function in both the source (joint) distribution and the distortion level. To obtain the error exponent, for the achievability part, we use the same generalized type covering lemma, and for the converse, we use the strong converse together with a change-of-measure technique. Finally, to obtain the moderate deviations constant, we apply the moderate deviations theorem to probabilities defined in terms of information spectrum quantities.

We derive the optimal second-order coding region and moderate deviations constant for successive refinement source coding with a joint excess-distortion probability constraint. We consider two scenarios: 1) a discrete memoryless source (DMS) and arbitrary distortion measures at the decoders and 2) a Gaussian memoryless source (GMS) and quadratic distortion measures at the decoders. For a DMS with arbitrary distortion measures, we prove an achievable second-order coding region, using type covering lemmas by Kanlis and Narayan and by No, Ingber, and Weissman. We prove the converse using the perturbation approach by Gu and Effros. When the DMS is successively refinable, the expressions for the second-order coding region and the moderate deviations constant are simplified and easily computable. For this case, we also obtain new insights on the second-order behavior compared with the scenario where separate excess-distortion proabilities are considered. For example, we describe a DMS, for which the optimal second-order region transitions from being characterizable by a bivariate Gaussian to a univariate Gaussian, as the distortion levels are varied. We then consider a GMS with quadratic distortion measures. To prove the direct part, we make use of the sphere covering theorem by Verger-Gaugry, together with appropriately-defined Gaussian type classes. To prove the converse, we generalize Kostina and Verdú's one-shot converse bound for point-to-point lossy source coding. We remark that this proof is applicable to general successively refinable sources. In the proofs of the moderate deviations results for both scenarios, we follow a strategy similar to that for the second-order asymptotics and use the moderate deviations principle.

We derive the optimal second-order coding region for the lossy Gray-Wyner source coding problem for discrete memoryless sources under mild conditions. To do so, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú (2012). The converse part uses the perturbation argument by Gu and Effros (2009) in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses a generalization of type covering lemmas and the uniform continuity of the conditional rate-distortion function in both the source joint distribution and the distortion level.

We derive the optimal second-order coding region for the discrete successive refinement source coding problem under the joint excess-distortion event. To do so, we define a generalization of the tilted information density and leverage its properties. In the achievability part, we make use of type covering lemmas by Kanlis and Narayan (1996) and by No, Ingber and Weissman (2015). In the converse proof, we make use of the perturbation approach by Gu and Effros (2009). We also specialize our results to successively refinable sources and provide an alternative converse proof for such sources by generalizing Kostina and Verdú's (2012) one-shot converse bound for point-to-point lossy source coding.