Transcript RST3

Two Tantalizing Concepts
• Randomness
– “Any one who considers arithmetical methods
of producing random digits is, of course, in a
state of sin” – Von Neumann
– There is no such thing as a random number;
there are only methods (e.g., arithmetic vs.
quantum) to produce random numbers
• Redundancy
– Narrow sense, in information theory
– Broad sense, in science and engineering
Pseudorandom Number Generator
• Complexity-based
pseudorandomness is a
deep concept in
theoretical CS (with wide
applications in scientific
computing such as Monte
Carlo methods)
• Engineers generate
pseudorandom numbers
by arithmetic algorithms
such as linear
congruential generators
and linear feedback shift
registers (LFSR)
A maximal LFSR produces an
m-sequence (i.e. cycles through
all possible 2n − 1 states within
the shift register except the state
where all bits are zero), unless it
contains all zeros, in which case
it will never change.
AWGN
• How is AWGN generated under MATLAB?
• Yes, by “randn” function but how does it
work?
• RANDN('seed') in MATLAB4 vs.
RANDN('state',J) in MATLAB5
• Subtle implication into denoising
experiments
Randomness in
Nature
Star Constellation
Waitomo Glow-worm Caves
on Lake Roturura
Random pin-dropping
Homogeneous Poisson
Redundancy
• What is redundancy in Shannon’s mind?
– In source coding, redundancy refers to the
gap between the source entropy and the
actual bit rate (so we want to eliminate
redundancy).
– In channel coding, redundancy refers to the
“extra bits” used for error correction (so we
add redundancy in a controlled fashion).
• Divide-and-conquer: an engineering
solution
Redundancy in Nature
• Redundancy in language
– Why are human languages redundant? How
is it possible for young kids to learn speaking
a language?
• Redundancy in natural world
– Why are natural images compressible? How
does human vision systems work?
• Redundancy in genetics
– Why are Chromosomes in pairs?
Redundancy in SP
• Sampling – an artificial tool which we have
not yet understood well
• No signal from the natural world is bandlimited
– Shannon/Nyquist’s sampling theorem never
holds in practice
– “Truth is much too complicated to allow
anything but approximations.”
• Uniform sampling- a “sin” operator?
Two Contrasting Views
• Redundancy is bad
– Since most natural signals are still so compressible,
we should acquire much fewer samples (joint design
of sampling and coding)
– The emerging “compressive sensing” paradigm
• Redundancy is good
– Redundancy is essential to human intelligence
especially the redundancy exploitation hypothesis
advocated by H. Barlow
– To solve high-level computer vision problems, get
low-level (image sampling, feature extraction) done
right first.