NDLI: Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity

Content Provider	IEEE Xplore Digital Library
Author	Vereshchagin, N.K. Vitányi, P.M.B.
Copyright Year	1963
Abstract	We examine the structure of families of distortion balls from the perspective of Kolmogorov complexity. Special attention is paid to the canonical rate-distortion function of a source word which returns the minimal Kolmogorov complexity of all distortion balls containing that word subject to a bound on their cardinality. This canonical rate-distortion function is related to the more standard algorithmic rate-distortion function for the given distortion measure. Examples are given of list distortion, Hamming distortion, and Euclidean distortion. The algorithmic rate-distortion function can behave differently from Shannon's rate-distortion function. To this end, we show that the canonical rate-distortion function can and does assume a wide class of shapes (unlike Shannon's); we relate low algorithmic mutual information to low Kolmogorov complexity (and consequently suggest that certain aspects of the mutual information formulation of Shannon's rate-distortion function behave differently than would an analogous formulation using algorithmic mutual information); we explore the notion that low Kolmogorov complexity distortion balls containing a given word capture the interesting properties of that word (which is hard to formalize in Shannon's theory) and this suggests an approach to denoising.
Sponsorship	IEEE Information Theory Society
Starting Page	3438
Ending Page	3454
Page Count	17
File Size	435298
File Format	PDF
ISSN	00189448
Volume Number	56
Issue Number	7
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-07-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Rate-distortion Noise reduction Distortion measurement Mutual information Shape Region 8 Frequency Measurement standards Rate distortion theory Information analysis shapes of curves Algorithmic rate distortion characterization denoising distortion families fitness of destination words individual data Kolmogorov complexity rate distortion
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising

Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity

The empirical distribution of rate-constrained source codes

Complexity-constrained trellis quantizers

An Operational Characterization of Mutual Information in Algorithmic Information Theory

Distortion Rate Function of Sub-Nyquist Sampled Gaussian Sources

Measuring meaningful information in images: algorithmic specified complexity

Empirical Mode Decomposition Technique With Conditional Mutual Information for Denoising Operational Sensor Data

Mutual Dimension

Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity

Similar Documents

Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising

Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity

The empirical distribution of rate-constrained source codes

Complexity-constrained trellis quantizers

An Operational Characterization of Mutual Information in Algorithmic Information Theory

Distortion Rate Function of Sub-Nyquist Sampled Gaussian Sources

Measuring meaningful information in images: algorithmic specified complexity

Empirical Mode Decomposition Technique With Conditional Mutual Information for Denoising Operational Sensor Data

Mutual Dimension

Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity