In this paper, robust linear adaptive filtering in presence of non-Gaussian noise is addressed. More precisely, the well-known algorithm for robust adaptive learning called minimum error entropy with fiducial points (MEEF) is challenged. Error entropy and error correntropy are two information theoretic cost functions that can be used in a supervised learning problem. They incorporate higher-order statistics of the error between labels and system outputs and therefore are comprehensive descriptors of data that show more robustness against non-Gaussianity of the environment compared to the conventional cost functions. This robustness makes them strong substitutions for classical mean square error (MSE) that only considers the variance (second-order moment) of the error. In minimum error entropy (MEE) specifically, error entropy is minimized to extract as much information as possible about the data generating system. However, this minimum entropy can also occur for other error PDFs not located at the origin inasmuch as entropy is shift-invariant. In these cases, an undesired estimate of the system parameters is obtained. Therefore, an extra step must be taken to concentrate error samples around the origin. The most celebrated approach towards that end is MEEF, in which some external and artificial zero error samples, called fiducial points (not generated by the underlying system), are added to the cost function as the reference points to force actual error samples to get concentrated around them. Using these fiducial points translates MEEF into a weighted combination of MEE and maximum correntropy criterion (MCC). In this paper, it is shown that incorporating these fiducial points into MEE can even degrade the steady state misalignment and/or convergence speed.

Minimum energy required to achieve a distortion-noise profile, i.e., a function indicating the maximum allowed distortion value for each channel noise level, is studied for transmission of Gaussian sources over Gaussian channels. A general coding scheme is proposed to upper bound the minimum energy needed for any distortion-noise profile. Conversely, utilizing a family of lower bounds originally derived for broadcast channels with power constraints, the minimum required energy is lower bounded for any profile. As examples, linear, exponential, square-law, and staircase profiles are studied. It is shown that for the linear profile, as well as for any concave profile, uncoded transmission is optimal. As a negative result, it is shown that exponential profiles are not achievable with finite energy. For square-law and staircase profiles, upper bounds and lower bounds are derived and the gaps between them are studied.

In this paper, minimum energy required to achieve a distortion-noise profile is studied for robust transmission of Gaussian sources over Gaussian channels when there is side information about the source at the receiver. The distortion-noise profile is a function indicating the maximum allowed distortion value for each channel noise level and side information quality, where neither are known at the transmitter. It is shown here that uncoded transmission is optimal for (inversely) linear profiles. Turning then to staircase profiles, a proposed coding scheme is studied to obtain an upper bound to the minimum energy needed. Conversely, a general family of lower bounds is derived for the minimum required energy and compared against the upper bound.

Asymptotic energy-distortion performance of zero- and low-delay transmission of Gaussian sources over energy-limited Gaussian channels is studied. A lower bound for the leading term in the negative logarithm of the distortion, termed the energy-distortion exponent, is derived through an achievable scheme based on high-resolution quantization coupled with orthogonal signaling. The higher-order term in the negative logarithm of the distortion, termed the energy-distortion dispersion, is optimized while keeping the leading term, the energy-distortion exponent, at its optimal (respectively, the best known) value for the zero-delay (respectively, low-delay) regime. In contrast with the decaying dispersion previously reported in the literature, the proposed coding scheme achieves a constant dispersion. When the scheme is optimized, this constant can be improved with respect to its naïve value, i.e., that achieved by optimizing purely the source coding performance instead of the end-to-end distortion. Lastly, a tradeoff of achievable energy-distortion exponents is derived for broadcast scenarios by extending the point-to-point scheme to include a successive refinement source coder coupled with two rounds of orthogonal signaling. A simple parametric computation algorithm is derived for the tradeoff.

In this paper, a modified version of maximum correntropy criterion (MCC) with application in online regression (or adaptive filtering) is proposed. It is well known that information theoretic criteria such as error correntropy criterion (ECC) and error entropy criterion (EEC) have the advantage of better performance in supervised learning problems like regression and adaptive filtering when the error between system output and labels (sometimes called desired signals) contains outliers and/or does not follow a Gaussian distribution. Specifically, we improve the existing adaptive maximum correntropy criterion algorithm (known as AMCC) by simply eliminating major outliers during learning process. This elimination leads to better steady state performance than previously known algorithms.

In this paper, we present new results on the achievable rate-distortion regions in networked scalable compression problems, based on a flexible codebook generation and binning method. First, we consider the problem of scalable coding in the presence of decoder side information, for which the prior work analyzed the two important cases the degraded side information where source X and the side information variables (Y1, Y2) form a Markov chain in the order of either X - Y1-Y2or X - Y2- Y1. First, we present an example non-Markov side information scenario where the proposed coding strategy achieves a strictly larger rate-distortion region compared to prior work. We then consider the problem of multi-user successive refinement where different users that are connected to a central server via links with different noiseless capacities strive to reconstruct the source in a progressive fashion. It is shown that a prior rate-distortion region is suboptimal in general, albeit its optimality for a Gaussian source with MSE distortion, and the proposed coding scheme achieves points beyond the achievable region of prior work.

In this paper, online linear regression in the presence of non-Gaussian noise is addressed. In such environments, there are outliers in error samples (error between system output and labels) and/or the error does not follow a Gaussian distribution. Information theoretic measures such as error entropy criterion (EEC) and error correntropy criterion (ECC) are known for their superior performance compared to mean square error (MSE) in these cases. In this paper, an efficient technique of running quantile estimation based on quantization of error samples is introduced alongside which correntropy leads to lower steady state misalignment compared to previous algorithms.

Minimum power required to achieve a distortion-noise profile, i.e., a function indicating the maximum allowed distortion value for each noise level, is studied for the transmission of Gaussian sources over Gaussian channels under a regime of bandwidth approaching zero. A simple but instrumental lower bound to the minimum required power for a given profile is presented. For an upper bound, a dirty-paper based coding scheme is proposed and its power-distortion tradeoff is analyzed. Finally, upper and lower bounds to the minimum power is analyzed and compared for specific distortion-noise profiles, namely rational profiles with order one and two.

Asymptotic energy-distortion performance of zero-delay communication under Gaussian broadcasting is investigated. The analysis can be motivated by the scenario where the same internet of things (IoT) device is transmitting its measurements to multiple control units that are experiencing varying noise levels. Using high-resolution analysis for quantizer design coupled with orthogonal signaling, the higher-order term in the negative logarithm of the distortion, termed the energy-distortion dispersion, is optimized while keeping the leading term, the energy-distortion exponent, at its optimal value for the zero-delay regime.

Standard method of types and large deviations techniques are utilized to analyze the accuracy of an electronic voting mechanism, where to protect the privacy of the voters, votes are randomly changed by the system before being transmitted. Special attention is given to referendum elections with only YES and NO votes are on the ballot, and a scheme where votes are flipped with a fixed probability. It is shown that the exponent of the probability of incorrectly calling the election can be well-approximated to be proportional to the square of how far the vote is from 50%-50%. This result is then leveraged to understand the interplay between number of voters, the allowed probability of incorrectly calling the election, and the level of privacy.

In this paper, we present a novel approach to find informative and anomalous samples in videos exploiting the concept of typicality from information theory. In most video analysis tasks, selection of the most informative samples from a huge pool of training data in order to learn a good recognition model is an important problem. Furthermore, it is also useful to reduce the annotation cost as it is time-consuming to annotate unlabeled samples. Typicality is a simple and powerful technique which can be applied to compress the training data to learn a good classification model. In a continuous video clip, an activity shares a strong correlation with its previous activities. We assume that the activity samples that appear in a video form a Markov chain. We explicitly show how typicality can be utilized in this scenario. We compute an atypical score for a sample using typicality and the Markovian property, which can be applied to two challenging vision problems-(a) sample selection for learning activity recognition models, and (b) anomaly detection. In the first case, our approach leads to a significant reduction of manual labeling cost while achieving similar or better recognition performance compared to a model trained with the entire training set. For the latter case, the atypical score has been exploited in identifying anomalous activities in videos where our results demonstrate the effectiveness of the proposed framework over other recent strategies.

In successive refinement of information, the decoder refines its representation of the source progressively as it receives more encoded bits. The rate-distortion region of successive refinement describes the minimum rates required to attain the target distortions at each decoding stage. In this paper, we derive a parametric characterization of the rate-distortion region for successive refinement of abstract sources. Our characterization extends Csiszár's result to successive refinement, and generalizes a result by Tuncel and Rose, applicable for finite alphabet sources, to abstract sources. This characterization spawns a family of outer bounds to the rate-distortion region. It also enables an iterative algorithm for computing the rate-distortion region, which generalizes Blahut's algorithm to successive refinement. Finally, it leads a new nonasymptotic converse bound. In all the scenarios where the dispersion is known, this bound is second-order optimal. In our proof technique, we avoid Karush-Kuhn-Tucker conditions of optimality, and we use basic tools of probability theory. We leverage the Donsker-Varadhan lemma for the minimization of relative entropy on abstract probability spaces.

Asymptotic energy-distortion performance of zero-and low-delay communication scenarios under additive white Gaussian noise (AWGN) is investigated. Using high-resolution analysis for quantizer design coupled with orthogonal signaling, the higher-order term in the negative logarithm of the distortion, termed the energy-distortion dispersion, is optimized while keeping the leading term, the energy-distortion exponent, at its optimal (respectively, the best known) value, for the zero-delay (respectively, low-delay) regime. In contrast with the decaying dispersion previously reported in the literature, the proposed coding scheme achieves a constant dispersion. When the scheme is optimized, this constant can be increased considerably with respect to its naive value, i.e., that achieved by optimizing purely the source coding performance instead of the end - to-end distortion.

Asymptotic energy-distortion performance of low-delay transmission of Gaussian sources over Gaussian broadcast channels is investigated. Achievable exponent tradeoffs for M- to-infinity mappings are derived for each M, and are shown to converge to the tradeoff of the Shannon-theoretic limits.

In computer vision, selection of the most informative samples from a huge pool of training data in order to learn a good recognition model is an active research problem. Furthermore, it is also useful to reduce the annotation cost, as it is time consuming to annotate unlabeled samples. In this paper, motivated by the theories in data compression, we propose a novel sample selection strategy which exploits the concept of typicality from the domain of information theory. Typicality is a simple and powerful technique which can be applied to compress the training data to learn a good classification model. In this work, typicality is used to identify a subset of the most informative samples for labeling, which is then used to update the model using active learning. The proposed model can take advantage of the inter-relationships between data samples. Our approach leads to a significant reduction of manual labeling cost while achieving similar or better recognition performance compared to a model trained with entire training set. This is demonstrated through rigorous experimentation on five datasets.

Minimum energy required to achieve a distortion-noise profile, i.e., a function indicating the maximum allowed distortion value for each noise level, is studied for robust transmission of Gaussian sources over Gaussian channels. It is shown that for the inversely linear profile, uncoded transmission is optimal. On the other hand, it turns out that exponential profiles are not achievable with finite energy. Finally, using a family of lower bounds and a proposed coding scheme, the minimum energy behavior for the square-law profile is understood up to a multiplicative constant.

In successive refinement of information, the decoder refines its representation of the source progressively as it receives more encoded bits. The rate-distortion region of successive refinement describes the minimum rates required to attain the target distortions at each decoding stage. In this paper, we derive a parametric characterization of the rate-distortion region for successive refinement of abstract sources. Our characterization extends Csiszar's result [1] to successive refinement, and generalizes a result by Tuncel and Rose [2], applicable for finite alphabet sources, to abstract sources. The new characterization leads to a family of outer bounds to the rate-distortion region. It also enables new nonasymptotic converse bounds.

This paper studies lossy transmission of a memoryless bivariate Gaussian source over a bandwidth-mismatched memoryless Gaussian broadcast channel with two receivers, where each receiver is interested in reconstructing only one source component. For both bandwidth expansion and compression regimes, novel hybrid digital/analog (HDA) coding schemes are proposed. With appropriate choice of parameters, our schemes are shown to specialize to separate source-channel coding studied by Gao and Tuncel, and is, therefore, superior to it in both bandwidth regimes. Our scheme for bandwidth expansion also outperforms the HDA coding scheme of Behroozi et al. On the other hand, if a proposed conjecture (supported by numerical observations) is indeed true, the same superiority follows for the bandwidth compression regime as well. Finally, when the bandwidth expansion/compression ratio approaches 1, both of our schemes become optimal as their performance approaches that of the bandwidth-matched scheme of Tian et al.

Lossy transmission of Gaussian sources over energy-limited Gaussian point-to-point and broadcast channels is studied under the infinite bandwidth regime, i.e., when the number of channel uses is unlimited. Using previously known asymptotic achievability and converse results, the energy-distortion exponent, defined as the rate of decay of the square-error distortion as the available energy-to-noise ratio increases without bound, is completely characterized for both the point-to-point and broadcast channel cases. Turning then to the scenario of zero-delay transmission, where outage events with arbitrarily small probability are allowed, it is shown that the same energy-distortion exponent as in the infinite-delay case can be achieved in all the studied scenarios.

The energy-distortion tradeoff for the transmission of a white Gaussian source over the additive white Gaussian broadcast channel is investigated by translating the known upper and lower bounds into the infinite bandwidth regime. While a gap continues to exist between the bounds in this regime, it is shown that in a certain region on the distortion plane, the energy difference between the best known upper and lower bounds is quantifiably small.

We consider the lossy transmission of a memoryless bivariate Gaussian source over an average-power-constrained bandwidth-mismatched Gaussian broadcast channel with two receivers where each receiver is interested in only one component. We propose new hybrid digital/analog coding schemes which are demonstrated to outperform the previously known schemes.

Zero-delay transmission of a Gaussian source over an additive white Gaussian noise (AWGN) channel is considered in the presence of an independent additive Gaussian interference signal. The mean squared error (MSE) distortion is minimized under an average power constraint assuming that the interference signal is known at the transmitter. Optimality of simple linear transmission does not hold in this setting due to the presence of the known interference signal. While the optimal encoder-decoder pair remains an open problem, various non-linear transmission schemes are proposed in this paper. In particular, interference concentration (ICO) and one-dimensional lattice (1DL) strategies, using both uniform and non-uniform quantization of the interference signal, are studied. It is shown that, in contrast to typical scalar quantization of Gaussian sources, a non-uniform quantizer, whose quantization intervals become smaller as we go further from zero, improves the performance. Given that the optimal decoder is the minimum MSE (MMSE) estimator, a necessary condition for the optimality of the encoder is derived, and the numerically optimized encoder (NOE) satisfying this condition is obtained. Based on the numerical results, it is shown that 1DL with non-uniform quantization performs closer (compared with the other schemes) to the NOE while requiring significantly lower complexity.

Zero-delay transmission of a Gaussian source is considered over an additive white Gaussian noise (AWGN) channel in the presence of an additive Gaussian interference signal. The mean squared error (MSE) distortion is minimized under an average power constraint assuming that the interference signal is known causally at the transmitter. Optimality of simple uncoded transmission does not hold in this setting due to the presence of the known interference signal, and various non-linear transmission schemes are proposed. In particular, interference concentration (ICO) and one-dimensional lattice (1DL) strategies are studied. It is shown that non-uniform quantization of the interference signal for ICO improves the performance.

An achievable scheme for zero-delay transmission of an i.i.d. Gaussian source over an additive white Gaussian noise channel with no bandwidth limitation is introduced, and its energy-distortion performance is analyzed. By the nature of the problem, one must transmit each source sample separately but can use the channel infinitely many times. The proposed scheme builds on separation of source and channel coding, whereby the source is quantized into “equiprobable” cells so that the output can be seen as a message suitable for channel coding. Moreover, as the number of quantization cells go to infinity, the channel capacity can be approached with arbitrarily small error. In the high energy-to-noise ratio regime, the minimum energy required to obtain a given distortion level in the proposed scheme can come as close as 3dB to the Shannon bound, which can only be achieved using infinite delay.

Delay limited transmission of a uniform source over an additive white Gaussian noise (AWGN) channel under an average power constraint is considered. Assuming that the channel can be used only once, mean squared error (MSE) distortion is studied for both the bandwidth matched, and the 2∶1 bandwidth compression cases. In the bandwidth matched scenario, simply scaling the source sample, i.e., analog transmission, performs better than transmitting the scalar quantized source samples. For the bandwidth compression scenario, a hybrid digital analog transmission scheme that quantizes the first source sample and superimposes the quantized sample with the scaled version of the second sample is studied. It is shown that, in this scheme, as opposed to the bandwidth matched case, a finite number of quantization indices minimizes the achievable distortion. The performance of this hybrid scheme is then compared with a numerically optimized encoder using the steepest decent algorithm iteratively. It is observed that the performance of the hybrid scheme is reasonably close to the numerically optimized scheme, while having a significantly lower computational complexity. The theoretical Ziv-Zakai (ZZ) bound on the average distortion is also considered to better understand the gap between the optimal performance and the proposed scheme.

An achievable scheme for zero-delay transmission of an i.i.d. Gaussian source over an additive white Gaussian channel with no bandwidth limitation is introduced, and its energy-distortion performance is analyzed. By the nature of the problem, one must transmit each source sample separately but can use the channel infinitely many times. We introduce an outage concept, and analyze the expected distortion conditioned on no outage. We show that the proposed scheme can approach to the asymptotical decay for large enough energy for arbitrary outage probability. The proposed scheme builds on separation of source and channel coding, whereby the source is quantized with a high-resolution optimal quantizer. In the high energy-to-noise ratio (ENR) regime, the minimum energy required to obtain a given distortion level in the proposed scheme can approach arbitrarily close the Shannon bound, which can only be achieved using infinite delay.

For transmission of memoryless Gaussian sources over channels with additive white Gaussian noise, the tradeoff between the distortion when the channel quality is good versus bad is investigated under the constraint that the distortion is optimal when the channel has the targeted median quality. The problem was proposed by Tian and Shamai, who subsequently proved remarkable achievability results for bandwidth expansion ratios k, which are integers or unit fractions, i.e., k = 2,3,4, ... or k =1/2,1/3,1/4,... Their result is extended here to all k≥2 and k≤1/2 by generalizing the hybrid digital/analog (HDA) scheme of Wilson et al. to the case of bandwidth mismatch. Finally, novel schemes are proposed for 1/2≤k<;1and 1<;k≤ 2 achieving nontrivial tradeoffs outperforming all known schemes. These latter schemes rely on another extension of the HDA scheme by Wilson et al., namely, the relaxation of the independence of source and channel input sequences.

The problem of scalable coding while exploiting the decoder side information is considered. Prior work considered the two important cases concerning the degraded side information where source X and the side information variables (Y1, Y2) form a Markov chain in the order of either X − Y1− Y2or X − Y2− Y1. While the encoding schemes for these settings differ considerably, they are both based on the combination of conditional codebook encoding, a standard tool in scalable coding, and random binning, conventionally used in decoder side information problems. In this paper, an encoding scheme is proposed solely on the basis of random binning, which essentially performs scalable and Wyner-Ziv coding simultaneously. Proposed scheme achieves the rate-distortion regions of prior results. A practical advantage of the unifying scheme is the fact that random binning can be realized via practical tools such as nested lattice codes and channel codes. Finally, motivated by the proposed encoding scheme, a network interpretation of scalable coding is considered. An achievable region is derived for this problem setting and the potential benefits of networked scalable coding are shown.

Exploration versus exploitation in a sensor field with a mobile agent is examined in the context of source coding. The encoder is the low complexity data gathering agent. The decoder is a high complexity fusion center. The encoder first sends a coarse description of the random field, then transmits a refined description of a region of interest, i.e., a subset of the correlated sources in the first stage and so on. The main source coding challenge is that the receiver wants to refine a subset of the correlated sources that is unknown to the encoder a priori. The conventional approach of scalable coding via conditional codebook encoding (CCE) requires a codebook that is exponential in size with respect to the number of sources and also the number of refinement stages. This paper studies an alternative approach, using random binning (RB), in lieu of CCE. The universality of RB plays a key role, as the encoder does not know a priori which sources the decoder wants to refine. It is shown that RB does not introduce any loss and can effectively replace CCE while providing significant storage reduction in terms of the number of codewords stored. Achievable rate regions are derived for the single and the multi-terminal encoding settings.

The problem of lossy transmission of a Gaussian source over an AWGN bandwidth-mismatched broadcast channel with three receivers is addressed. The tradeoff between the distortion levels at the good and the bad receivers is tackled when the distortion at the median receiver is required to be optimal. The problem was proposed by Tian and Shamai (2008), who subsequently found in the work of Tian and Shamai (2011) remarkable achievability results for bandwidth expansion ratios κ which are integers or unit fractions, i.e., κ = 2, 1/3, 1/5, etc. Their result is extended here to all κ ≥ 2 and κ ≤ 1/2 by generalizing the hybrid digital/analog (HDA) scheme in the work of Wilson et al. (2010) to the case of bandwidth mismatch. Finally, novel schemes are proposed for 1/2 = κ ≤ 1 and 1 <; κ ≤ 2 achieving nontrivial tradeoffs.

This paper studies zero-delay joint source-channel coding (JSCC) of Gaussian sources over additive white Gaussian noise (AWGN) channels in the Wyner-Ziv scenario, that is, when there is side information about the source available only to the receiver. The proposed encoding scheme is based on hybrid digital-analog (HDA) transmission in a zero-delay fashion. Specifically, to achieve zero-delay, after applying scalar quantization to the source, the properly scaled analog information (quantization error) is superimposed on the scaled digital information (quantized source), and then transmitted. At the receiver side, several reconstruction schemes are analyzed. It is shown that all the schemes, when optimized, are superior to existing uncoded, digital, or hybrid transmission methods. It is also shown that the proposed HDA transmission may result in increased robustness to channel and/or side information mismatch compared to uncoded transmission. Observing that the bandwidth-matched Wyner-Ziv problem is intimately related to the coding scenario without side information but with bandwidth expansion factor 2, the proposed scheme is applied to the latter problem. It is shown that this application results in a better performance than the well-known inverse spiral mapping.

A high-dimensional database system is studied where the noisy versions of the underlying feature vectors are observed in both the enrollment and query phases. The noisy observations are compressed before being stored in the database, and the user wishes to both identify the correct entry corresponding to the noisy query vector and reconstruct the original feature vector within a desired distortion level. A fundamental capacity-storage-distortion tradeoff is identified for this system in the form of single-letter information theoretic expressions. The relation of this problem to the classical Wyner-Ziv rate-distortion problem is shown, where the noisy query vector acts as the correlated side information available only in the lossy reconstruction of the feature vector.

Lossy transmission of a Gaussian source over an additive white Gaussian (AWGN) channel with side information at the decoder is tackled under the regime of bandwidth expansion. A previously known scheme, hybrid digital/analog Wyner-Ziv (HDA-WZ) coding is shown to remain optimal when extended from the bandwidth matched case to the bandwidth expansion case. The extended scheme also exhibits similar robustness properties under mismatched side information and/or channel quality. Finally, under the criterion of min-max distortion loss, the extended HDA-WZ scheme is shown to outperform a purely-digital scheme known as the common description scheme (CDS).

The problem of transmitting a pair of correlated Gaussian sources over degraded broadcast channels using optimal separate source and channel codes is studied. Upper bounds are derived for the rate penalty (in terms of channel uses per source symbol) and the power loss endured by separate coding compared to joint coding. Although source-channel separation is suboptimal in general, it is demonstrated that the performance of separate coding comes close to that of optimal joint coding, especially for low distortion pairs. In fact, in some cases, separate coding performs better than the best known joint schemes so far. It is also shown analytically that separate coding is optimal when either of the sources is to be reconstructed in a near-lossless fashion.

The tradeoff between the number of distinguishable objects and search speed in a data management system is investigated in an information-theoretic framework. In the discussed scenario, incoming high-dimensional (and noisy) data vectors are enrolled in (possibly multiple) clusters to be accessed later. Upon receiving a random query, which is the noisy version of an enrolled vector, the search engine retrieves only a subset of the clusters to compare against the query. This creates tension between the search speed (determined by the expected number of retrieved entries) and recognition capacity (maximum possible number of entries that can be reliably recognized). A single-letter achievable rate region is characterized and it is shown with examples that search can be performed much faster in the discussed scenario than in non-clustered linear scan without compromising maximum recognition capacity.

We study the zero-delay joint source-channel coding problem of transmitting a Gaussian source over a Gaussian channel in the presence of side information known only to the receiver. To achieve zero-delay, after applying scalar quantization to the source, the properly scaled analog information, namely the quantization error, is superimposed on the scaled digital information, i.e., the quantized source, and then transmitted. At the decoder, two decoding schemes are proposed, both of which estimate digital component first, followed by the analog component. It is shown that both schemes, when optimized over all related parameters, are superior to pure analog transmission for high enough correlation between source and side information. The robustness of one of the proposed HDA schemes against varying channel and side information conditions is also compared with that of the purely analog scheme.

The problem of broadcasting a pair of correlated Gaussian sources using optimal separate source and channel codes is studied. Considerable performance gains over previously known separate source-channel schemes are observed. Although source-channel separation yields suboptimal performance in general, it is shown that the proposed scheme is very competitive for any bandwidth compression/expansion scenarios. In particular, for a high channel SNR scenario, it can be shown to achieve optimal power-distortion tradeoff.

A new hybrid digital/analog scheme is proposed for lossy transmission of a Gaussian source over a bandwidth-matched Gaussian broadcast channel with source side information available at each receiver. The proposed scheme combines two schemes that were previously shown to achieve optimal point-to-point distortion/power tradeoff simultaneously at all receivers under two distinct conditions stated in terms of channel and side information quality parameters. For the two-receiver case, the combined scheme is shown to achieve the same kind of optimality for the entire region in the parameter space sandwiched between those two conditions. Crucial to this result is a new degree of freedom discovered in designing point-to-point hybrid digital/analog schemes with side information. When superimposed with analog transmission, the proposed scheme outperforms all previously known schemes even outside the optimality region in the parameter space.

A new hybrid digital/analog scheme is proposed for lossy transmission of a Gaussian source over a two-receiver bandwidth-matched Gaussian broadcast channel with source side information available at each receiver. The proposed scheme makes use of a new level of freedom for point-to-point transmission and combines two previously known schemes that are optimal under two different conditions regarding channel and side information quality parameters. It is shown that for the entire intermediate region in the parameter space sandwiched between those two conditions, the proposed scheme can achieve the same distortion-power tradeoff as in point-to-point transmission simultaneously for both channels, and is therefore optimal.

A noisy database system is studied in which the noisy versions of the underlying feature vectors are observed in both the enrollment and the query phases. The noisy observations are compressed before being stored in the database, and the user wishes both to identify the correct entry corresponding to the noisy query vector and to reconstruct the original feature vector within a desired distortion requirement. A fundamental capacity/storage/distortion tradeoff is identified for this system in the form of single-letter information theoretic expressions. The relation of this problem to the classical Wyner-Ziv rate-distortion problem is shown, where the noisy query vector acts as the correlated side information in the lossy reconstruction of the feature vector.

Two new schemes are proposed for transmitting a Gaussian source over a Gaussian channel. These schemes directly generalize previous results of Bross and Puri A scaled version of either the source itself or the quantization error is superimposed on the digital information, and thus serves as effective channel state information (CSI) unknown to the receiver. It is shown that for any power allocation between the coded and uncoded components of transmission, optimal distortion can be achieved by a continuum of auxiliary random variables (rather than only Costa's) if the decoded auxiliary codeword is properly used. This observation provides a new degree of freedom in point-to-point transmission. This freedom, in turn, can be utilized in multiterminal scenarios, as is demonstrated with an example.

This paper addresses lossy transmission of a common source over a broadcast channel when there is correlated side information at the receivers, with emphasis on the quadratic Gaussian and binary Hamming cases. A digital scheme that combines ideas from the lossless version of the problem, i.e., Slepian-Wolf coding over broadcast channels, and dirty paper coding, is presented and analyzed. This scheme uses layered coding where the common layer information is intended for both receivers and the refinement information is destined only for one receiver. For the quadratic Gaussian case, a quantity characterizing the combined quality of each receiver is identified in terms of channel and side information parameters. It is shown that it is more advantageous to send the refinement information to the receiver with ¿better¿ combined quality. In the case where all receivers have the same overall quality, the presented scheme becomes optimal. Unlike its lossless counterpart, however, the problem eludes a complete characterization.

The successive refinement problem is extended to vector sources where individual distortion constraints are posed on each vector component. For vector Gaussian sources with squared-error distortion, a single-letter rate-distortion characterization is inherited from the previously studied Gaussian multiple descriptions problem with covariance distortion constraints. Though this characterization is amenable to well-known numerical convex optimization techniques, an analytical solution is difficult to obtain in full generality even for 2-D sources. In this work, the special case of successive refinability is addressed analytically. Specifically, vector Gaussian sources are shown to benotsuccessively refinable everywhere unlike scalar Gaussian sources. It is also shown that, for 2-D Gaussian sources, the rate loss at the second stage can be as high as 0.5 b/sample in a ¿degenerate¿ scenario corresponding to what is known as sequential coding of correlated sources. Finally, analysis of 2-D binary symmetric sources with Hamming distortion reveals that the behavior of these sources with respect to successive refinability exhibits remarkable similarity to their 2-D Gaussian counterparts.

The authors modify the conventional DPCM framework of motion-compensated video coding to improve its error resilience in a packet loss environment. The authors propose a system with two decoding modes based on whether a packet is lost or not, so as to minimize the combined distortion due to quantization and transmission errors.

A predictive scheme for zero-delay Wyner-Ziv coding of sources with memory is proposed and analyzed in the high-resolution regime for Gaussian source-side information pairs. Incorporating the propagation of distortion due to occasional decoding errors into the analysis, the quantizers and first-order filter parameters are simultaneously optimized. The rate-distortion performance of the scheme is compared with those of non-distributed coding and Wyner-Ziv coding with a naive choice of prediction filters (minimizing temporal correlation), as well as the asymptotic Wyner-Ziv rate-distortion function.

The significance of the rate transfer argument used in a class of two-stage source and channel coding problems is discussed. A very simple necessary and sufficient condition is derived as to when the argument helps expand the achievability region. Special attention is paid to several example scenarios such as successive refinement with or without side information, and degraded broadcast channels. Finally, for reliable separate source-channel coding, whether a test based on comparing marginal source and channel rate regions is more restrictive than comparing cumulative rate regions, obtained after using the rate transfer argument, is discussed. It turns out that if rate transfer does not matter in either the source or the channel coding problem, the two tests are equivalent.

The tradeoff between storage and identification rates for multiple databases is investigated from an information theoretic perspective. In the assumed model, noisy observations of feature vectors of two distinct groups, called the ancestors, are compressed and stored in two separate databases. When queried with a noisy observation of a (possibly random) function of two randomly selected ancestors (one from each group), the system is required to correctly identify the ancestors with high probability. Single-letter inner and outer bounds are presented on the set of achievable rate points, which identify a tradeoff between the compression rates and the identification rate region: the lower the compression rates for storage, the larger the rate region achievable for identification.

The rate-distortion (RD) problem for two-layer coding of a pair(X,Y) of correlated sources is considered. The first layer information enables reconstruction ofXwithin a certain distortionDX, while reception of both layers additionally enables reconstruction ofYwithin distortionDY. Although this problem is a special case of the successive refinement problem, the computation of the RD region for this scenario is nontrivial. Using a general class of outer bounds (analogous to Shannon lower bound in the classical RD theory) to the successive refinement rate-distortion region, the successive coding RD region for the case where(X,Y) is a jointly Gaussian pair and the distortion measure is squared-error is explicitly characterized.

The asymptotic tradeoff between the number of distinguishable objects and the necessary storage space (or equivalently, the search complexity) in an identification system is investigated. In the discussed scenario, high-dimensional (and noisy) feature vectors extracted from objects are first compressed and then enrolled in the database. When the user submits a random query object, the extracted noisy feature vector is compared against the compressed entries, one of which is output as the identified object. The first result this paper presents is a complete single-letter characterization of achievable storage and identification rates (measured in bits per feature dimension) subject to vanishing probability of identification error as the dimensionality of feature vectors becomes very large. This single-letter characterization is then extended for a multistage system whereby depending on the number of entries, the identification is performed by utilizing part or all of the recorded bits in the database. Finally, it is shown that a necessary and sufficient condition for a two-stage system to achieve single-stage capacities at each stage is Markovity of the optimal test channels.

It has been recently discovered that complementary graph entropy characterizes (and offers new insights into) the minimum asymptotic rate for zero-error source coding with decoder side information. This paper presents new results that build on and complement this discovery. Specifically, i) previously unknown subadditivity properties of complementary graph entropy are derived, and ii) zero-error coding rates are characterized in terms of complementary graph entropy for two multiterminal coding scenarios. For both scenarios, the rate characterization implies no rate loss relative to point-to-point source coding.

This paper deals with the design of coding schemes for transmitting a source over a broadcast channel when there is source side information at the receivers. Based on Slepian-Wolf coding over broadcast channels, three hybrid digital/analog schemes are proposed and their power-distortion tradeoff is investigated for Gaussian sources and Gaussian broadcast channels. All three transmit the same digital and analog information but with varying coding order. Although they are not provably optimal in general, they can significantly outperform uncoded transmission and separate source and channel coding.

This paper analyzes the problem of hierarchical channel coding for memoryless channels: given a codebook at a particular power level, if the allowed power level is increased, the expanded codebook is generated by pairwise addition of elements from the existing codebook and an auxiliary codebook. This is the counterpart of the problem of additive successive refinement in source coding. The supported set of rates in the channel coding scenario is fully characterized in this paper. The behavior of hierarchical coding schemes is analyzed for some representative channels. It is shown that for many common channels, hierarchical coding does not entail a loss of capacity at either layer.

This paper deals with the design of scalar quantizers for source coding with side information at the decoder. In the fixed length scenario, under high-resolution assumptions, the optimal level density is shown to be periodic. The operational rate-distortion performance is then characterized. The performance of variable length codes with uniform quantization is also characterized.

This paper deals with the design of coding schemes for lossy transmission of a source over a broadcast channel when there is correlated side information at the receivers. Using ideas from Slepian-Wolf coding over broadcast channels and dirty paper coding, new schemes are presented and their rate-distortion performance is derived. For the binary Hamming and quadratic Gaussian scenarios, when the source and the channel bandwidths are equal, it is shown that these schemes are sometimes optimal and that they can outperform both separate source and channel coding, and uncoded transmission.

We propose a novel approach based on predictive quantization (PQ) for online summarization of multiple time-varying data streams. A synopsis over a sliding window of most recent entries is computed in one pass and dynamically updated in constant time. The correlation between consecutive data elements is effectively taken into account without the need for preprocessing. We extend PQ to multiple streams and propose structures for real-time summarization and querying of a massive number of streams. Queries on any subsequence of a sliding window over multiple streams are processed in real time. We examine each component of the proposed approach, prediction, and quantization separately and investigate the space-accuracy trade-off for synopsis generation. Complementing the theoretical optimality of PQ-based approaches, we show that the proposed technique, even for very short prediction windows, significantly outperforms the current techniques for a wide variety of query types on both synthetic and real data sets.

The rate-distortion problem for two-layer coding of a pair (X,Y) of correlated sources is considered. The first layer information enables reconstruction of X within a certain distortion Dx, while reception of both layers additionally enables reconstruction of Y within distortion Dy. While this problem is a special case of the successive refinement problem, the computation of the rate-distortion region for this scenario is non- trivial. Using a general class of outer bounds to the successive refinement rate-distortion region, the successive coding rate- distortion region for the case where (X, Y) is a jointly Gaussian pair and the distortion measure is squared-error is explicitly characterized.

The asymptotic tradeoff between the number of distinguishable objects and the necessary storage space (or equivalently, the search complexity) in an identification system was characterized previously. This paper extends that single-letter characterization to the multi-stage scenario whereby data is stored in increasing levels of accuracy, and depending on the number of entries, the identification is performed by utilizing part or all of the recorded bits in the database. It is also shown that a sufficient condition for a multi-stage system to achieve single-stage capacities at each stage is Markovity of the optimal test channels. Whether Markovity is also necessary remains elusive.

This paper tackles the problem of zero-error instantaneous coding with decoder side information in light of the Kraft inequality. Specifically, a bounded Kraft sum over all cliques in the characteristic graph of the source/side-information pair is envisioned to be a sufficient condition for the existence of a valid code with given codeword lengths. It is shown that (i) if such a sufficient condition exists for a class of graphs, it is possible to universally bound the rate redundancy in the class, (ii) there exist graph classes of interest for which such sufficient conditions can indeed be found, and finally (iii) no such condition can be found for the class of all graphs.

For certain source coding problems, it is well known that the Kraft inequality provides a simple sufficient condition for the existence of codes with given codeword lengths. Motivated by this fact, a sufficient condition based on the Kraft inequality can also be sought for the problem of zero-error instantaneous coding with decoder side information. More specifically, it can be envisioned that a sufficient condition for the existence of such codes with codeword lengths{ιx}is that for some0<α<1Σ/xϵF(2-lx)≤α for each cliqueFin the characteristic graphGof the source-side information pair. In this correspondence, it is shown that (1) if the above is indeed a sufficient condition for a class 𝒢 of graphs, then it is possible to come as close as 1-log2α bits to the asymptotic limits for each graph in 𝒢, 2) there exist graph classes of interest for which such α can indeed be found, and finally (3) no such α can be found for the class of all graphs.

We present a novel distributed video coding algorithm based on transform coding of distributed sources and exploiting the geometrical relationships between the location of the sensors. The geometry is used to align the video sequences and distributed quantization of transform coefficients is used to eliminate spatial and inter-sensor redundancy. In contrast with most of the current video compression standards which only exploit spatial and temporal dundancy within each video sequence, we also consider the significant redundancy between the sequences. Results demonstrate that our algorithm yields a significant saving in bit rate on the overlapping portion of multiple views.

We present a novel 3D model-based distributed video coding algorithm. It is based on independent, model-based tracking of multiple sources and distributed coding of the tracked feature points. The model-based tracking scheme provides correspondence between the overlapping set of features that are visible in the different views. While the motion estimates obtained from the tracking algorithm remove temporal redundancy and the 3D model accounts for removing spatial redundancy, distributed coding is used to eliminate inter-sensor redundancy. Thus, in contrast to most of the current video compression standards which only exploit spatial and temporal redundancy within each video sequence, we also consider the significant redundancy between the sequences. Results demonstrate that our algorithm yields a significant saving in bit rate on the overlapping portion of multiple views.

The asymptotic tradeoff between the number of distinguishable objects and the necessary storage space in an identification system is investigated. In the discussed scenario, high-dimensional (and noisy) feature vectors extracted from objects are first compressed and then enrolled in the database. When the user submits a random query object, the extracted noisy feature vector is compared against the compressed entries, one of which is output as the identified object. This paper presents a complete single-letter characterization of achievable storage and identification rates (measured in bits per feature dimension) subject to vanishing probability of identification error as the dimensionality of feature vectors becomes very large

This correspondence presents a novel application of the theta function defined by Lovasz. The problem of coding for transmission of a source through a channel without error when the receiver has side information about the source is analyzed. Using properties of the Lovasz theta function, it is shown that separate source and channel coding is asymptotically suboptimal in general. By contrast, in the case of vanishingly small probability of error, separate source and channel coding is known to be asymptotically optimal. For the zero-error case, it is further shown that the joint coding gain can in fact be unbounded. Since separate coding simplifies code design and use, conditions on sources and channels for the optimality of separate coding are also derived

We discuss reliable transmission of a discrete memoryless source over a discrete memoryless broadcast channel, where each receiver has side information (of arbitrary quality) about the source unknown to the sender. When there are K=2 receivers, the optimum coding strategy using separate and stand-alone source and channel codes is to build two independent binning structures and send bin indices using degraded message sets through the channel, yielding a full characterization of achievable rates. However, as we show with an example, generalization of this technique to multiple binning schemes does not fully resolve the K>2 case. Joint source-channel coding, on the other hand, allows for a much simpler strategy (i.e., with no explicit binning) yielding a successful single-letter characterization of achievable rates for any Kges2. This characterization, which utilizes a trivial outer bound to the capacity region of general broadcast channels, is in terms of marginal source and channel distributions rather than a joint source-channel distribution. This contrasts with existing results for other multiterminal scenarios and implies that optimal schemes achieve "operational separation." On the other hand, it is shown with an example that an optimal joint source-channel coding strategy is strictly advantageous over the combination of stand-alone source and channel codes, and thus "informational separation" does not hold

Two different aspects of distributed source coding is discussed. First, a previously developed distributed uniform scalar quantization method is improved by adopting non-uniform quantization. It is observed that compared to uniform quantization, the non-uniform scheme further approaches to the distortion-rate bound by 0.5 bit. Turning then to sources with memory, the tradeoff between exploitation of time and space correlation is exposed. It is shown by example that optimal transforms deviate from their traditional counterparts. Specifically, optimal transforms in the distributed framework do not necessarily fully decorrelate each sequence in time

Lossless transmission of a source across a broadcast channel, where the decoders have side information about the source (unknown to the encoder), is discussed. Adopting separate source and channel coding strategies translates to sending hierarchical information, or degraded message sets, as is more commonly known, through the channel. Joint source-channel coding, on the other hand, allows for a simpler strategy, which turns out to be optimal. As a result, a complete single-letter characterization of achievable rates is successfully derived. This characterization surprisingly depends solely on the source and the channel marginal distributions. Finally, it is shown by an example that joint source-channel coding can be advantageous over the coding strategy which utilizes optimal source and channel codes separately

The classical characterization of achievable error exponents in binary hypothesis testing is generalized in two different directions. First, in M-ary hypothesis testing, the tradeoff of all M(M - 1) types of error exponents and corresponding optimal decision schemes are explored. Then, motivated by a power-constrained distributed detection scenario, binary hypothesis testing is revisited, and the tradeoff of power consumption versus error exponents is fully characterized. In the latter scenario, sensors are allowed to make random decisions as to whether they should remain silent and save power, or transmit and improve detection quality. It is then shown by an example that optimal sensor decisions may indeed be random

The classical result of Blahut, which characterizes achievable error exponents in binary hypothesis testing, is generalized in two different directions. First, in M-ary hypothesis testing, the tradeoff of all M(M-1) types of error exponents and corresponding optimal decision schemes are explored. Then, motivated by a power-constrained distributed detection scenario, binary hypothesis testing is revisited, and the tradeoff of power consumption versus error exponents is fully characterized. In the latter scenario, sensors are allowed to make random decisions as to whether they should remain silent and save power, or transmit and improve detection quality. It is then shown by an example that optimal sensor decisions may indeed be random

This correspondence focuses on a significant distinction between two hierarchical type covering strategies, namely, weak and strong covering, and on the impact of this distinction on known results. In particular, it is demonstrated that the rate region for weak covering, whose natural use is in scalable source coding, is generally larger than the rate region for strong covering, which is primarily useful in hierarchical guessing. This correspondence also presents a corrected converse result for the hierarchical guessing problem.

Inspired by a converse result, the concept of "probabilistically matched" sources and channels is extended to sources subject to multiresolution coding and degraded broadcast channels. Unlike in the point-to-point communication scenarios, however, due to the lack of a separation principle or a complete characterization for achievable cost-distortion triplets, matching of the source and the channel constitutes only a sufficient condition for optimality.

A basic problem in information theory is source coding under a distortion constraint when the decoder has side-information about the source. In this paper the problem of variable length coding of a memoryless source under a maximum distortion constraint when there is side-information solely at the decoder is focused. Using a combinatorial approach, a nonsingle-letter expression for the minimum asymptotic average rate as well as single-letter bounds on this rate is derived

This paper derives sufficient conditions for obtaining optimal multiresolution joint source-channel coding across degraded broadcast channels. We then specialize this condition to the case of single-letter codes, and define probabilistic matching accordingly.

This paper describes the guessing subject to rate-distortion theory. The concept of type covering is the set of vectors with the identical distortion balls. The main use of hierarchical type covering was the determination of achievable error exponents in scalable source coding. Weak covering is sufficient for that purpose. Strong covering is necessary for hierarchical guessing. The two covering strategies and their characterizations lead to different rate regions.

A lossy coding scheme is proposed for separate encoding and joint decoding of two correlated sequences. The algorithm simultaneously exploits the correlation between the sequences (using a binning-based quantization scheme) and that between the samples of each sequence (using linear prediction). Under the proposed coding regime, optimal prediction filter design fundamentally deviates from the traditional approach. More specifically, it is, in general, not optimal to employ first-order prediction for noisy observations of a first-order Markov source, even when the noise is negligibly small. Moreover, even if the prediction filter is constrained to be of degree 1, the optimal filter coefficient is different from the correlation coefficient of the Markov source. In the particular example treated in this paper, it is shown that optimal first- and second-order prediction respectively enjoy up to 0.9 dB and 1.15 dB improvement over the traditional approach.

This paper investigates the relationship between rate-distortion theory and efficient content-based data retrieval from high-dimensional databases. We consider database design as the encoding of a data object sequence, and retrieval from the database as the decoding of the sequence using side information (i.e., the query) available only at the decoder. We show that, in this setting, the optimal asymptotic tradeoff between the search time R/sub s/ (bits per data object read from the storage device) and the expected search accuracy D/sub s/ (relevance of the retrieved data set) is given by the Wyner-Ziv solution with a side-information-dependent distortion measure. Moreover, the data indexing and retrieval problem is, in general, inseparable from the data compression problem. Data items selected by the search procedure, which can be stored in the disk with a limited total rate of R/sub r/ /spl ges/ R/sub s/, need to be presented at a prescribed expected reconstruction quality D/sub r/. This is, hence, a problem of scalable source coding or successive refinement, albeit with differing layer distortion measures to quantify search and reconstruction quality, respectively. We derive a single-letter characterization of all achievable quadruples {R/sub s/,R/sub r/,D/sub s/,D/sub r/}, and prove conditions for "successive refinability" without rate loss. Finally, we show that the special case D/sub s/=D/sub r/=0 is nontrivial and of practical interest in this context, as it can impose "acceptable" search and reconstruction qualities for each individual data item and for the entire query space with high probability, in contradistinction with standard average distortion requirements. The region of achievable {R/sub s/,R/sub r/} is obtained by adapting Rimoldi's characterization to a new regular scalable coding problem.

Let (X,Y) be a pair of random variables distributed over a finite product set V/spl times/W according to a probability distribution P(x,y). The following source coding problem is considered: the encoder knows X, while the decoder knows Y and wants to learn X without error. The minimum zero-error asymptotic rate of transmission is shown to be the complementary graph entropy of an associated graph. Thus, previous results in the literature provide upper and lower bounds for this minimum rate (further, these bounds are tight for the important class of perfect graphs). The algorithmic aspects of instantaneous code design are considered next. It is shown that optimal code design is NP-hard. An optimal code design algorithm is derived. Polynomial-time suboptimal algorithms are also presented, and their average and worst case performance guarantees are established.

The problem of separate zero-error coding of correlated sources is considered. Inner and outer single-letter bounds are established for the achievable rate region, and conditions for their coincidence are investigated. It is shown that successive encoding combined with time sharing is not always an optimal coding strategy. Conditions for its optimality are derived. The inner bound to the achievable rate region follows as a special case of the single-letter characterization of a generalized zero-error multiterminal rate-distortion problem. The applications of this characterization to a problem of remote computing are also explored. Other results include (i) a product-space characterization of the achievable rates, (ii) bounds for finite block length, and (iii) asymptotic fixed-length rates.

The characterization of the set of achievable rate and distortion values for scalable source coding is extended to additionally account for error exponents, namely, the negative normalized asymptotic log likelihood of error events at different layers. The "error" at each layer is defined as the event that the source block is not reproduced within the prespecified fidelity at the corresponding decoder. We consider separate error events at each layer so as to allow a tradeoff analysis for the error exponents when the rate and distortion values are fixed. For two-step coding of discrete memoryless sources, we derive a single-letter characterization of the region of all achievable 6-tuples (R/sub 1/, R/sub 2/, E/sub 1/, E/sub 2/, D/sub 1/, D/sub 2/), i.e., the rate, error exponent, and distortion levels at each layer. We also analyze the special case of successive refinability, where (R/sub 1/, E/sub 1/, D/sub 1/) and (R/sub 2/, E/sub 2/, D/sub 2/) individually achieve the nonscalable bounds. A surprising outcome of the analysis is that for any D/sub 1/, D/sub 2/, and E/sub 1/, there exists a finite threshold E/spl circ//sub 2//spl ges/E/sub 1/ such that successive refinability is ensured for all E/sub 2//spl ges/E/spl circ//sub 2/.

Methods for determining and computing the rate-distortion (RD) bound for N-layer scalable source coding of a finite memoryless source are considered. Optimality conditions were previously derived for two layers in terms of the reproduction distributions q/sub y1/ and q/sub y2/|y/sub 1/. However, the ignored and seemingly insignificant boundary cases, where q/sub y1/=0 and q/sub y2/|y/sub 1/ is undefined, have major implications on the solution and its practical application. We demonstrate that, once the gap is filled and the result is extended to N-layers, it is, in general, impractical to validate a tentative solution, as one has to verify the conditions for all conceivable q/sub yi+1/,...,y/sub N/|y/sub 1/,...,y/sub i/ at each (y/sub 1/,...,y/sub i/) such that q/sub y1/,...,y/sub i/=0. As an alternative computational approach, we propose an iterative algorithm that converges to the optimal joint reproduction distribution q/sub y1/,...,y/sub N/, if initialized with q/sub y1/,...,y/sub N/>0 everywhere. For nonscalable coding (N=1), the algorithm specializes to the Blahut-Arimoto (1972) algorithm. The algorithm may be used to directly compute the RD bound, or as an optimality testing procedure by applying it to a perturbed tentative solution q. We address two additional difficulties due to the higher dimensionality of the RD surface in the scalable (N>1) case, namely, identifying the sufficient set of Lagrangian parameters to span the entire RD bound; and the problem of efficient navigation on the RD surface to compute a particular RD point.

Rate-distortion bounds for scalable coding, and conditions under which they coincide with nonscalable bounds, have been extensively studied. These bounds have been derived for the general tree-structured refinement scheme, where reproduction at each layer is an arbitrarily complex function of all encoding indexes up to that layer. However, in most practical applications (e.g., speech coding) "additive" refinement structures such as the multistage vector quantizer are preferred due to memory limitations. We derive an achievable region for the additive successive refinement problem, and show via a converse result that the rate-distortion bound of additive refinement is above that of tree-structured refinement. Necessary and sufficient conditions for the two bounds to coincide are derived. These results easily extend to abstract alphabet sources under the condition E{d(X,a)}

Let finite source and reproduction alphabets X and Y and a distortion measure d: X/spl times/Y/spl rarr/[0,/spl infin/) be given. We study the minimum asymptotic rate required to describe a source distributed over X within a (given) distortion threshold D at every sample. The problem is hence a min-max problem, and the distortion measure is extended to vectors as follows: for x/sup n//spl isin/X/sup n/, y/sup n//spl isin/Y/sup n/, d(x/sup n/, y/sup n/)=max/sub i/d(x/sub i/, y/sub i/). In the graph-theoretic formulation we introduce, a code for the problem is a dominating set of an equivalent distortion graph. We introduce a linear programming lower bound for the minimum dominating set size of an arbitrary graph, and show that this bound is also the minimum asymptotic rate required for the corresponding source. Turning then to the optimality of scalar coding, we show that scalar codes are asymptotically optimal if the underlying graph is either an interval graph or a tree.

We propose an iterative optimization algorithm for the generic class of clustering-based indexing for approximate similarity searching. It was previously shown that clustering is a powerful component of approximate searching that reduces the number of retrieved data points. The objective of the proposed algorithm is to maximize the expected search quality given the query distribution. The problem is decomposed into minimization over three mapping functions, and fixed-point iterations of the algorithm alternately optimizing one mapping while fixing the other two. We demonstrate via experiments on real high dimensional data sets that the algorithm significantly improves the time/accuracy efficiency over heuristic clustering design.

In this paper, we introduce a novel indexing technique based on efficient compression of the feature space for approximate similarity searching in large multimedia databases. Its main novelty is that state-of-the-art tools from the discipline of data compression are adopted to optimize the complexity-performance tradeoff in large data sets. The design procedure optimizes the query access time by jointly accounting for both database distribution and query statistics. We achieve efficient compression by using appropriate vector quantization (VQ) techniques, namely, multi-stage VQ and split-VQ, which are especially suited for limited memory applications. We partition the data set using the accumulated query history, and each partition of data points is separately compressed using a vector quantizer tailored to its distribution. The employed VQ techniques inherently provide a spectrum of points to choose from on the time/accuracy plane. This property is especially crucial for large multimedia databases where I/O time is a bottleneck, because it offers the flexibility to trade time for better accuracy. Our experiments demonstrate speedups of 20 to 35 over a VA-file technique that has been adapted for approximate nearest neighbor searching.

Develops a general framework for approximate nearest-neighbor queries. We categorize the current approaches for nearest-neighbor query processing based on either their ability to reduce the data set that needs to be examined, or their ability to reduce the representation size of each data object. We first propose modifications to well-known techniques to support the progressive processing of approximate nearest-neighbor queries. A user may therefore stop the retrieval process once enough information has been returned. We then develop a new technique based on clustering that merges the benefits of the two general classes of approaches. Our cluster-based approach allows a user to progressively explore the approximate results with increasing accuracy. We propose a new metric for evaluation of approximate nearest-neighbor searching techniques. Using both the proposed and the traditional metrics, we analyze and compare several techniques with a detailed performance evaluation. We demonstrate the feasibility and efficiency of approximate nearest-neighbor searching. We perform experiments on several real data sets and establish the superiority of the proposed cluster-based technique over the existing techniques for approximate nearest-neighbor searching.

With the proliferation of multimedia data, there is increasing need to support the indexing and searching of high dimensional data. Recently, a vector approximation based technique called VA-file has been proposed for indexing high dimensional data. It has been shown that the VA-file is an effective technique compared to the current approaches based on space and data partitioning. The VA-file gives good performance especially when the data set is uniformly distributed. Real data sets are not uniformly distributed, are often clustered, and the dimensions of the feature vectors in real data sets are usually correlated. More careful analysis for nonuniform or correlated data is needed for effectively indexing high dimensional data. We propose a solution to these problems and propose the VA+-file, a new technique for indexing high dimensional data sets based on vector approximations. We conclude with an evaluation of nearest neighbor queries and show that the VA+-file technique res...

A novel video-object segmentation algorithm is proposed, which takes the previously estimated 2-D dense motion vector field as input and uses the generalized recursive shortest spanning tree method to approximate each component of the motion vector field as a piecewise planar function. The algorithm is successful in capturing 3-D planar objects in the scene correctly, with acceptable accuracy at the boundaries. The proposed algorithm is fast and requires no initial guess about the segmentation mask. Moreover, it is a hierarchical scheme which gives finest to coarsest segmentation results. The only external parameter needed by the algorithm is the number of segmented regions that essentially control the level at which the coarseness the algorithm would stop. The proposed algorithm improves the "analysis model" developed in the European COST211 framework.

Flexibility and efficiency of coding, content extraction, and content-based search are key research topics in the field of interactive multimedia. Ongoing ISO MPEG-4 and MPEG-7 activities are targeting standardization to facilitate such services. European COST Telecommunications activities provide a framework for research collaboration. At present a significant effort of the COST 211/sup ter/ group activities is dedicated toward image and video sequence analysis and segmentation-an important technological aspect for the success of emerging object-based MPEG-4 and MPEG-7 multimedia applications. The current work of COST 211 is centered around the test model, called the analysis model (AM). The essential feature of the AM is its ability to fuse information from different sources to achieve a high-quality object segmentation. The current information sources are the intermediate results from frame-based (still) color segmentation, motion vector based segmentation, and change-detection-based segmentation. Motion vectors, which form the basis for the motion vector based intermediate segmentation, are estimated from consecutive frames. A recursive shortest spanning tree (RSST) algorithm is used to obtain intermediate color and motion vector based segmentation results. A rule-based region processor fuses the intermediate results; a postprocessor further refines the final segmentation output. The results of the current AM are satisfactory.

Object segmentation and tracking are problems within the scope of MPEG-4 and MPEG-7 standardization activities. A novel algorithm for both object segmentation and tracking is presented. The algorithm fuses motion, color, and accumulated previous segmentation data at 'region level', in contrast to conventional 'pixel level' approaches. The information fusion is achieved by a rule-based region processing unit which intelligently utilizes the motion information to locate the objects in the scene, the color information to extract the true boundaries, and the segmentation result of the previous frame for tracking the objects. The algorithm is generic in the sense that the modules prior to the rule-based region processor can independently be replaced by alternative units which can achieve the same tasks. In the proposed algorithm, while the recursive-shortest-spanning-tree (RSST) algorithm is used for segmentation purposes, hierarchical-block-matching (HBM) is utilized for estimating motion between frames. The simulation results are very promising for this novel object segmentation approach.