LR-003416 · Signal Processing
PROVENAbbe diffraction resolution criterion
Conventional coherent periodic-structure resolution criterion requiring capture of diffraction orders.
Loading
Limits RegistryRegistry collection
Proven Limits in Information Theory
Accepted information-theoretic bounds on communication, coding, compression, and signal recovery.
40 published records in this collectionLR-003408 · Signal Processing
PROVENBalian–Low localization limitation
A critical-density Gabor Riesz basis cannot have a window well localized in both time and frequency.
LR-003204 · Information Theory
PROVENBand-limited Gaussian channel capacity
Shannon–Hartley capacity of an ideal band-limited Gaussian channel.
LR-003404 · Signal Processing
PROVENBayesian Cramér–Rao lower bound
Van Trees lower bound combines expected data Fisher information and prior information.
LR-003202 · Information Theory
PROVENBinary erasure channel capacity
Capacity of a binary erasure channel with erasure probability epsilon.
LR-003201 · Information Theory
PROVENBinary symmetric channel capacity
Capacity of a binary symmetric channel with crossover probability p.
LR-003213 · Information Theory
PROVENChannel finite-blocklength normal approximation
Second-order approximation to maximal code size at blocklength n and error epsilon.
LR-003403 · Signal Processing
PROVENCramér–Rao estimator-variance lower bound
Covariance of an unbiased estimator is bounded below by inverse Fisher information.
LR-003215 · Information Theory
PROVENData-processing inequality
Information cannot increase under stochastic post-processing.
LR-003207 · Information Theory
PROVENDegraded wiretap-channel secrecy capacity
Perfect-secrecy capacity of a degraded discrete memoryless wiretap channel.
LR-003200 · Information Theory
PROVENDiscrete memoryless channel capacity
Shannon capacity of a finite discrete memoryless channel.
LR-003205 · Information Theory
PROVENDiscrete memoryless multiple-access capacity region
Capacity region of a stationary memoryless multiple-access channel.
LR-003411 · Signal Processing
PROVENDonoho–Tanner compressed-sensing phase transition
Gaussian compressed sensing with basis pursuit has a sharp asymptotic sparsity–undersampling transition.
LR-003214 · Information Theory
PROVENFano inequality error floor
Conditional-entropy bound induced by any estimator's error probability.
LR-003407 · Signal Processing
PROVENGabor time–frequency uncertainty equality
Using cyclic frequency, Gaussian windows uniquely attain the minimum uncertainty product up to symmetries.
LR-003212 · Information Theory
PROVENGaussian source rate-distortion function
Squared-error rate-distortion function of an iid zero-mean Gaussian source.
LR-003220 · Information Theory
PROVENGilbert–Varshamov achievable coding bound
Greedy lower bound on the size of a binary code with prescribed minimum Hamming distance.
LR-003406 · Signal Processing
PROVENHeisenberg time–angular-frequency uncertainty bound
Time and angular-frequency standard deviations of a finite-energy signal obey the Fourier uncertainty principle.
LR-003413 · Signal Processing
PROVENJohnson–Lindenstrauss embedding dimension
N Euclidean points admit a low-dimensional embedding preserving all pairwise distances within 1±epsilon.
LR-003209 · Information Theory
PROVENKraft–McMillan code-length bound
Necessary and sufficient length inequality for a binary prefix code.
LR-003402 · Signal Processing
PROVENLandau necessary sampling-density bound
Stable sampling density cannot be below occupied spectral measure when frequency is measured in hertz.
LR-003218 · Information Theory
PROVENLempel–Ziv asymptotic compression limit
Universal Lempel–Ziv coding converges to entropy rate for stationary ergodic finite-alphabet sources.
LR-003210 · Information Theory
PROVENLossless finite-blocklength optimal error converse
Exact best error probability for fixed-length almost-lossless coding of a discrete source block.
LR-DRAFT-NYQUIST · Signal Processing
PROVENNyquist sampling limit
The Nyquist–Shannon sampling theorem sets the minimum rate at which a continuous signal must be sampled to be perfectly reconstructed — sample too slowly and distinct frequencies become indistinguishable (aliasing).
LR-003401 · Signal Processing
PROVENNyquist zero-ISI symbol-rate bound
Maximum zero-inter-symbol-interference symbol rate of an ideal real baseband channel of bandwidth B.
LR-003420 · Signal Processing
PROVENPapoulis generalized-sampling aggregate-density bound
A bank of generalized sampling channels must collectively provide Nyquist density to reconstruct an arbitrary B-bandlimited signal.
LR-003206 · Information Theory
PROVENPhysically degraded broadcast-channel capacity region
Two-user capacity region for a physically degraded discrete memoryless broadcast channel.
LR-003211 · Information Theory
PROVENRate-distortion function
Minimum asymptotic lossy coding rate for a memoryless source and single-letter distortion.
LR-003415 · Signal Processing
PROVENRayleigh circular-aperture resolution criterion
Conventional Rayleigh angular/separation criterion for two incoherent point sources through an ideal circular aperture.
LR-003203 · Information Theory
PROVENReal AWGN channel capacity
Capacity per use of a real discrete-time additive white Gaussian noise channel.
LR-003208 · Information Theory
PROVENShannon lossless source-coding entropy floor
Minimum asymptotic rate for lossless coding of a stationary memoryless source.
LR-003414 · Signal Processing
PROVENShannon number time–bandwidth degrees of freedom
Approximately 2BT eigenmodes are well concentrated in both a time interval of duration T and two-sided baseband bandwidth B.
LR-003418 · Signal Processing
PROVENSlepian maximum time–band concentration
Maximum in-interval energy fraction of a bandlimited signal is the largest prolate-spheroidal concentration eigenvalue.
LR-003216 · Information Theory
PROVENSlepian–Wolf distributed compression region
Lossless separate-encoder rate region for two correlated memoryless sources.
LR-003412 · Signal Processing
PROVENSparse-recovery spark uniqueness bound
Every k-sparse solution of Ax=y is unique exactly when the measurement matrix spark exceeds 2k.
LR-003219 · Information Theory
PROVENSphere-packing converse for discrete memoryless channels
Classical sphere-packing upper bound on the reliability exponent above critical rate.
LR-003410 · Signal Processing
PROVENSubgaussian RIP compressed-sensing measurement bound
A subgaussian measurement matrix satisfies k-order restricted isometry with high probability at logarithmic oversampling.
LR-003409 · Signal Processing
PROVENWelch coherence bound
M unit vectors in an N-dimensional complex space cannot all have smaller pairwise coherence.
LR-003217 · Information Theory
PROVENWyner–Ziv rate-distortion bound
Rate-distortion function with correlated side information only at the decoder.
LR-003405 · Signal Processing
PROVENZiv–Zakai estimation-error lower bound
Estimation MSE is bounded through binary hypothesis-testing error probabilities.