Victoria Kostina

Dr. Victoria Kostina

Electrical Engineering,California Institute of Technology, 1200 E California Blvd, MC 136-93, Pasadena, CA 91125, USA

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 April 2019 in IEEE Transactions on Automatic Control
Verified
Journal Article
Closed access
VKVictoria Kostina
Victoria Kostina
BHBabak Hassibi
Babak Hassibi
Consider a control problem with a communication channel connecting the observer of a linear stochastic system to the controller. The goal of the controller is to minimize a quadratic cost function in the state variables and control signal, known as the linear quadratic regulator (LQR). We study the fundamental tradeoff between the communication rate r bits/sec and the expected cost b. We obtain a lower bound on a certain rate-cost function, which quantifies the minimum directed mutual information between the channel input and output that is compatible with a target LQR cost. The rate-cost function has operational significance in multiple scenarios of interest: among others, it allows us to lower-bound the minimum communication rate for fixed and variable length quantization, and for control over noisy channels. We derive an explicit lower bound to the rate-cost function, which applies to the vector, non-Gaussian, and partially observed systems, thereby extending and generalizing an earlier explicit expression for the scalar Gaussian system, due to Tatikonda el al. [2]. The bound applies as long as the differential entropy of the system noise is not $-\infty$ . It can be closely approached by a simple lattice quantization scheme that only quantizes the innovation, that is, the difference between the controller's belief about the current state and the true state. Via a separation principle between control and communication, similar results hold for causal lossy compression of additive noise Markov sources. Apart from standard dynamic programming arguments, our technical approach leverages the Shannon lower bound, develops new estimates for data compression with coding memory, and uses some recent results on high resolution variablelength vector quantization to prove that the new converse bounds are tight.

9 March 2018 in Entropy
Verified
Journal Article
Open access
PDF file
AMArnaud Marsiglietti
Arnaud Marsiglietti
VKVictoria Kostina
Victoria Kostina
We derive a lower bound on the differential entropy of a log-concave random variable X in terms of the p-th absolute moment of X. The new bound leads to a reverse entropy power inequality with an explicit constant, and to new bounds on the rate-distortion function and the channel capacity. Specifically, we study the rate-distortion function for log-concave sources and distortion measure d ( x , x ^ ) = | x − x ^ | r , with r ≥ 1 , and we establish that the difference between the rate-distortion function and the Shannon lower bound is at most log ( π e ) ≈ 1 . 5 bits, independently of r and the target distortion d. For mean-square error distortion, the difference is at most log ( π e 2 ) ≈ 1 bit, regardless of d. We also provide bounds on the capacity of memoryless additive noise channels when the noise is log-concave. We show that the difference between the capacity of such channels and the capacity of the Gaussian channel with the same noise power is at most log ( π e 2 ) ≈ 1 bit. Our results generalize to the case of a random vector X with possibly dependent coordinates. Our proof technique leverages tools from convex geometry.

24 February 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
VKVictoria Kostina
Victoria Kostina
YPYury Polyanskiy
Yury Polyanskiy
SVSergio Verd
Sergio Verd
This paper quantifies the fundamental limits of variable-length transmission of a general (possibly analog) source over a memoryless channel with noiseless feedback, under a distortion constraint. We consider excess distortion, average distortion, and guaranteed distortion (d-semifaithful codes). In contrast to the asymptotic fundamental limit, a general conclusion is that allowing variable-length codes and feedback leads to a sizable improvement in the fundamental delaydistortion tradeoff. In addition, we investigate the minimum energy required to reproduce k source samples with a given fidelity after transmission over a memoryless Gaussian channel, and we show that the required minimum energy is reduced with feedback and an average (rather than maximal) power constraint.

10 September 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
RYRecep Can Yavas
Recep Can Yavas
VKVictoria Kostina
Victoria Kostina
MEMichelle Effros
Michelle Effros
This paper presents finite-blocklength achievability bounds for the Gaussian multiple access channel (MAC) and random access channel (RAC) under average-error and maximal-power constraints. Using random codewords uniformly distributed on a sphere and a maximum likelihood decoder, the derived MAC bound on each transmitter’s rate matches the MolavianJazi-Laneman bound (2015) in its first- and second-order terms, improving the remaining terms to $\frac {1}2\frac {\log {n}}{n}+{O} \left ({\frac {1}{n}}\right)$ bits per channel use. The result $\vphantom {\sum ^{R}}$ then extends to a RAC model in which neither the encoders nor the decoder knows which of ${K}$ possible transmitters are active. In the proposed rateless coding strategy, decoding occurs at a time ${n}_{t}$ that depends on the decoder’s estimate ${t}$ of the number of active transmitters ${k}$ . Single-bit feedback from the decoder to all encoders at each potential decoding time ${n}_{i}$ , ${i} \leq {t}$ , informs the encoders when to stop transmitting. For this RAC model, the proposed code achieves the same first-, second-, and third-order performance as the best known result for the Gaussian MAC in operation.

28 December 2020 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
RYRecep Can Yavas
Recep Can Yavas
VKVictoria Kostina
Victoria Kostina
MEMichelle Effros
Michelle Effros
Consider a random access communication scenario over a channel whose operation is defined for any number of possible transmitters. As in the model recently introduced by Polyanskiy for the Multiple Access Channel (MAC) with a fixed, known number of transmitters, the channel is assumed to be invariant to permutations on its inputs, and all active transmitters employ identical encoders. Unlike the Polyanskiy model, in the proposed scenario, neither the transmitters nor the receiver knows which transmitters are active. We refer to this agnostic communication setup as the Random Access Channel (RAC). Scheduled feedback of a finite number of bits is used to synchronize the transmitters. The decoder is tasked with determining from the channel output the number of active transmitters, $k$ , and their messages but not which transmitter sent which message. The decoding procedure occurs at a time ${n}_{t}$ depending on the decoder’s estimate, $t$ , of the number of active transmitters, $k$ , thereby achieving a rate that varies with the number of active transmitters. Single-bit feedback at each time ${n}_{i}, {i} \leq {t}$ , enables all transmitters to determine the end of one coding epoch and the start of the next. The central result of this work demonstrates the achievability on a RAC of performance that is first-order optimal for the MAC in operation during each coding epoch. While prior multiple access schemes for a fixed number of transmitters require $2^{k} - 1$ simultaneous threshold rules, the proposed scheme uses a single threshold rule and achieves the same dispersion.

1 March 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
VKVictoria Kostina
Victoria Kostina
This paper considers lossy source coding n-dimensional memoryless sources and shows an explicit approximation to the minimum source coding rate required sustain the probability of exceeding distortion d no greater than E, which is simpler than known dispersion-based approximations. Our approach takes inspiration in the celebrated classical result stating that the Shannon lower bound rate-distortion function becomes tight in the limit d → We formulate an abstract version of the Shannon lower bound that recovers both the classical Shannon lower bound and the rate-distortion function itself as special cases. Likewise, we show that a nonasymptotic version of the abstract Shannon lower bound recovers all previously known nonasymptotic converses. necessary and sufficient condition for the Shannon lower bound to be attained exactly is presented. It is demonstrated that whenever that condition is met, the rate-dispersion function given simply by the varentropy of the source. Remarkably, finite alphabet sources with balanced distortion measures satisfy that condition in the range of low distortions. Most continuous sources violate that condition. Still, we show that lattice quantizers closely approach the nonasymptotic Shannon lower bound, provided that the source density is smooth enough and the distortion is low. This implies that fine multidimensional lattice coverings are nearly optimal in the rate-distortion sense even at finite n. The achievability proof technique is based new bound on the output entropy of lattice quantizers terms of the differential entropy of the source, the lattice cell size, and a smoothness parameter of the source density. The technique avoids both the usual random coding argument and the simplifying assumption of the presence of a dither signal.