# Signal Processing

## Introduction
Signal processing is the art and science of extracting meaning from the world around us. It's the hidden hand that transforms raw data from the analog world – the sights, sounds, and sensations we experience – into the digital language of computers. This allows us to analyze, interpret, and manipulate information in ways that were once unimaginable.

### Core Concepts and Challenges
At its core, signal processing involves several fundamental concepts:

* **Acquisition:** Capturing analog signals from the real world using sensors, microphones, or other devices.
* **Representation:** Converting these continuous analog signals into discrete digital representations that computers can process.
* **Transformation:** Modifying and enhancing these digital signals to extract meaningful information, remove noise, or improve quality.
* **Analysis:** Interpreting and understanding the information contained within the signals, often using techniques like frequency analysis, pattern recognition, and statistical modeling.

### Mathematical Foundations
The field rests on a strong mathematical foundation, drawing from diverse areas like:

* **Fourier analysis:** Decomposing signals into their constituent frequencies to reveal hidden patterns.
* **Linear algebra:** Using matrices and vectors to represent and manipulate signals efficiently.
* **Probability and statistics:** Modeling and analyzing signals with uncertainty and randomness.
* **Information theory:** Quantifying and optimizing the information content of signals.

### Applications Abound
The applications of signal processing are vast and ever-expanding, impacting fields like:

* **Communication:** Enabling clear and reliable transmission of information through wired and wireless networks.
* **Entertainment:** Delivering high-quality audio and video experiences through streaming services and multimedia devices.
* **Medicine:** Providing advanced imaging techniques for diagnosis and treatment, such as MRI and CT scans.
* **Science:** Analyzing data from telescopes, microscopes, and other scientific instruments to unlock the secrets of the universe.

## Data Compression: Foundations Laid by Claude Shannon
This section explores the fundamental principles of data compression, a field heavily influenced by Claude Shannon's work in information theory. Efficient data compression is essential for managing the ever-growing volume of digital data, from streaming media to storing vast information libraries.

### Core Concepts
Before delving into compression techniques, it's important to understand these key concepts:

* **Sampling:** The process of converting continuous analog data into a discrete digital representation, forming the basis for digital processing.
* **Coding (Compression):** Transforming data into a more compact binary representation (sequences of 0s and 1s) to reduce storage space and transmission bandwidth.
* **Error-Correcting Code:** Adding redundancy to coded data to protect it against errors during storage or transmission. (This topic is not explored further in this section of the note.)

### Encoding and Decoding: A Two-Step Process
Data compression involves two fundamental steps: encoding and decoding. Encoding translates the data into a compact code, while decoding reconstructs the original data from the code.

#### Transformation
This step converts a sequence of symbols (letters, numbers, pixel values, etc.) into a binary code. Each symbol is assigned a unique binary codeword.

* **Example:** Grayscale Image Encoding In grayscale images, pixel values representing shades of gray are transformed into binary codes.

#### Coding Schemes
Different coding schemes optimize binary representation based on data characteristics and desired compression efficiency.

* **Uniform Coding:**
* Assigns codewords of equal length to all symbols.
* Simple, but inefficient when symbol frequencies vary significantly.
* Example: A grayscale image with 4 gray levels $(0, 1, 2, 3)$ could use 2-bit uniform codes: `0 -> 00`, `1 -> 01`, `2 -> 10`, `3 -> 11`.
* **Variable-Length Coding:**
* Assigns codewords of varying lengths based on symbol frequency. More frequent symbols get shorter codes.
* Offers better compression when symbol frequencies are uneven.
* Average codeword length: $L = \sum_i p_i l_i$ (where $p_i$ is the probability of the $i$-th symbol and $l_i$ is the length of its codeword).
* **Example:** If gray level '2' is more frequent, a variable-length code might be: `0 -> 001`, `1 -> 01`, `2 -> 1`, `3 -> 000`.
* **Prefix Coding:**
* A special type of variable-length code where no codeword is a prefix of another.
* Ensures unambiguous decoding.
* Satisfies the Kraft-McMillan Inequality: $\sum_i 2^{-l_i} \leq 1$
* **Example:** The variable-length code above is also a prefix code.
* **Decoding Trees:**
* A visual representation of prefix codes using a binary tree structure.
* Each codeword is a path from the root to a leaf.
* Facilitates decoding by traversing the tree according to the encoded bits.

### Shannon's Insights: Limits and Optimization
Shannon's work introduced crucial concepts for understanding the theoretical limits of data compression:

* **Probabilistic Modeling:** Analyzing coding efficiency by assuming symbols are generated based on a probability distribution, even if the exact message is unknown.
* **Entropy $H$:**
* Quantifies the average information content or uncertainty of a source.
* Represents the theoretical lower bound on average bits per symbol.
* $H = - \sum_v p_v \cdot \log_2 p_v$
* $0 \leq H \leq \log_2 N$ (where $N$ is the number of possible symbols)
* **Example:** A source with symbols A (probability 0.8) and B (probability 0.2) has entropy $H \approx 0.72$.
* **Shannon's Source Coding Theorem:**
* Establishes a fundamental limit: $H \leq L$ (where $L$ is the average codeword length).
* No lossless compression scheme can achieve an average codeword length shorter than the source's entropy.
* **Approaching the Limit:**
* **Huffman Coding:** A widely used algorithm for constructing optimal prefix codes, ensuring $H \leq L \leq H+1$.
* **Arithmetic Coding:** Another near-optimal technique that can achieve the Shannon limit for infinitely long sequences.
* **Information Transformation:**
* Exploiting dependencies in data (e.g., through predictive coding or transform coding) to reduce entropy and further improve compression.
* **Example:** Encoding differences between pixel values instead of the values themselves.

## Image Processing
Digital images are everywhere in our modern world, from capturing memories to facilitating scientific discoveries. Image processing empowers us to manipulate and analyze these images, extracting meaningful information and transforming them for various purposes. This note explores the fundamental concepts and techniques behind image processing.

### Image Fundamentals
This section covers the essential elements that constitute a digital image and how we perceive them.

#### What is a Digital Image?
A digital image is a numeric representation of a visual scene, composed of a grid of discrete elements called pixels. Essentially, it's a matrix of numbers that computers can understand and manipulate.

#### Pixels: The Building Blocks
* **Structure:** Pixels are the smallest unit of a digital image, arranged in a two-dimensional grid (rows and columns). Each pixel carries a numerical value representing its color or intensity.
* **Resolution:** The number of pixels in an image determines its resolution. Higher resolution means more pixels, leading to finer details and sharper images.
* **Spatial Sampling:** The process of converting a continuous scene into discrete pixels is called spatial sampling. The sampling rate affects the level of detail captured in the digital image.

#### Types of Images
* **Grayscale Images:** These images use a single value to represent the intensity of light at each pixel, typically ranging from 0 (black) to 255 (white).
* **Color Images:** These images use multiple values to represent different colors at each pixel. The most common model is RGB, where each pixel has three values for red, green, and blue light intensities.

#### Color Representation
* **RGB Color Model:** Based on additive color mixing, where red, green, and blue light are combined in various proportions to create a wide spectrum of colors.
* **Other Color Models:** While RGB is widely used for displays, other models like CMYK (Cyan, Magenta, Yellow, Key/Black) are used in printing, and other specialized color spaces exist for specific applications.

### Image Representation and Storage
Digital images, composed of vast arrays of pixels, need efficient ways to be stored and represented within computer systems. This section delves into how images are digitally represented and the techniques used to store them efficiently.

#### Digital Encoding of Image Data
* **Binary Representation:** At the most fundamental level, all digital data, including images, is stored as sequences of bits (0s and 1s). Each pixel's color or intensity value is converted into its binary equivalent.
* **Bit Depth and Color Encoding:**
* **Grayscale:** In grayscale images, the bit depth determines the number of gray levels. A common bit depth is 8, allowing for 256 shades of gray ($2^8 = 256$).
* Color: Color images typically use 8 bits per channel (red, green, blue) in the RGB model, resulting in 24 bits per pixel and a potential for millions of colors ($2^{24}$).

#### Image File Formats
Different file formats have emerged to store image data, each with its own characteristics and advantages:

* **JPEG (Joint Photographic Experts Group):** A widely used lossy compression format that achieves high compression ratios, making it suitable for photographs and web images.
* **PNG (Portable Network Graphics):** A lossless compression format that supports transparency and is often used for graphics and images with sharp lines and text.
* **GIF (Graphics Interchange Format):** Supports lossless compression and limited animation, often used for simple graphics and animations.
* **TIFF (Tagged Image File Format):** A versatile format that can be lossless or lossy, often used for professional photography and high-quality images.
* **BMP (Bitmap):** An uncompressed format that stores pixel data directly, resulting in large file sizes but preserving all image details.

#### Compression Techniques
Compression techniques aim to reduce the storage space required for images without significantly compromising their visual quality.

* **Lossless Compression**
* Preserves all original image data. The image can be perfectly reconstructed from the compressed file.
* **Techniques:**
* **Run-Length Encoding (RLE):** Encodes sequences of identical data values as a single value and count, efficient for images with large areas of uniform color.
* **Huffman Coding:** Assigns shorter codes to frequently occurring pixel values and longer codes to less frequent ones.
* **Lempel-Ziv-Welch (LZW):** Builds a dictionary of recurring patterns in the image data.
* **Lossy Compression**
* Achieves higher compression ratios by selectively discarding less perceptually important image data.
* **Techniques:**
* **Chroma Subsampling:** Exploits the human eye's lower sensitivity to color detail by reducing the resolution of color information while maintaining luminance resolution. 
* **Quantization:** Reduces the number of bits used to represent each pixel value, effectively reducing the number of distinct colors or intensity levels. 
* **Transform Coding:** Transforms the image data into a different domain (e.g., using Discrete Cosine Transform in JPEG) where it can be more efficiently compressed by discarding high-frequency components.

#### Choosing the Right Format and Compression
The choice of file format and compression technique depends on the specific needs of the application:

* **Lossless compression** is preferred when preserving all image details is crucial, such as in medical imaging or archival purposes.
* **Lossy compression** is suitable for applications where some loss of quality is acceptable in exchange for smaller file sizes, like web images and digital photography.
* **File format** selection considers factors like required image quality, support for transparency, animation needs, and compatibility with different software.

### Image Enhancement Techniques
Image enhancement techniques aim to improve the visual quality of an image or to emphasize specific features for better analysis. These techniques manipulate the image data to make it more suitable for display, interpretation, or further processing.

#### Spatial Domain Techniques
These techniques operate directly on the pixel values of the image.

* **Point Operations:** Modify the intensity of individual pixels independently.
* **Contrast Stretching:** Expands the range of intensity values in an image to increase contrast.
* **Histogram Equalization:** Distributes pixel intensities more evenly across the histogram, often enhancing contrast in images with poor dynamic range.
* **Gamma Correction:** Adjusts the nonlinear relationship between pixel values and display brightness, often used to correct for the characteristics of different display devices.
* **Thresholding:** Converts a grayscale image to a binary image by setting pixels above a certain threshold to white and those below to black.
* **Neighborhood Operations:** Modify a pixel's value based on the values of its neighboring pixels.
* **Smoothing (Low-pass Filtering):** Reduces noise and detail by averaging or weighting the pixel values within a local neighborhood. Examples include mean filtering, Gaussian filtering, and median filtering.
* **Sharpening (High-pass Filtering):** Enhances edges and details by emphasizing differences in intensity between neighboring pixels.

#### Frequency Domain Techniques
These techniques manipulate the image in the frequency domain after applying transforms like the Fourier Transform.

* **Low-pass Filtering:** Attenuates high-frequency components, which correspond to fine details and noise, resulting in a smoother image.
* **High-pass Filtering:** Attenuates low-frequency components, which correspond to overall brightness and large-scale features, emphasizing edges and details.
* **Band-pass Filtering:** Allows a specific range of frequencies to pass through, useful for selective enhancement or noise removal.

#### Color Image Enhancement
* **Color Balancing:** Adjusts the relative intensities of the red, green, and blue channels to correct for color casts or achieve a desired aesthetic effect.
* **Color Enhancement:** Increases the saturation or vividness of colors.
* **Tone Mapping:** Compresses the dynamic range of an image to make it displayable on devices with a limited range, often used for HDR (High Dynamic Range) images.

#### Choosing the Right Technique
The choice of image enhancement technique depends on the specific image, the desired outcome, and the application. Factors to consider include:

* **Type of image:** Different techniques are suitable for different types of images (e.g., photographs, medical images, satellite images).
* **Image quality:** The presence of noise, blur, or poor contrast can influence the choice of technique.
* **Desired outcome:** Whether the goal is to enhance details, remove noise, adjust contrast, or correct colors.

### Image Analysis Techniques
Image analysis techniques go beyond enhancing visual quality; they aim to extract meaningful information and insights from images. These techniques enable computers to "understand" the content of images, paving the way for applications like object recognition, medical image analysis, and autonomous navigation.

#### Feature Extraction
Identifying and extracting salient features is crucial for many image analysis tasks.

* **Edge Detection:** Detecting edges, or boundaries between objects or regions, is fundamental.
* **Gradient-based Methods:** Use image gradients (changes in intensity) to identify edges, such as the Sobel operator.
* **Canny Edge Detector:** A multi-stage algorithm that produces thin and accurate edges.
* **Corner Detection:** Corners are points of rapid change in image intensity in two directions, providing important structural information.
* **Harris Corner Detector:** Identifies corners based on the eigenvalues of the image gradient matrix.
* **Blob Detection:** Blobs are regions in an image that differ in properties like color or texture from the surrounding area.
* **Laplacian of Gaussian (LoG):** Detects blobs by finding zero-crossings in the second derivative of the image.

#### Segmentation
Segmentation partitions an image into meaningful regions or objects.

* **Thresholding:** Separates objects from the background based on intensity thresholds.
* **Region-based Segmentation:** Groups pixels based on similarity in properties like color, texture, or intensity.
* **Edge-based Segmentation:** Uses edge detection to identify boundaries and separate regions.
* **Clustering:** Groups pixels into clusters based on their feature similarity.

#### Object Recognition and Classification
Recognizing and classifying objects within images is a core task in computer vision.

* **Template Matching:** Compares a template image with regions in the input image to find matches.
* **Feature-based Recognition:** Extracts features from objects and uses classifiers (e.g., Support Vector Machines) to categorize them.
* **Deep Learning:** Employs convolutional neural networks (CNNs) to learn complex patterns and features for accurate object recognition.

#### Image Understanding
Higher-level analysis involves interpreting the scene and relationships between objects.

* **Scene Understanding:** Analyzing the overall context of the image, including object relationships and spatial layout.
* **Image Captioning:** Generating textual descriptions of the image content.
* **Visual Question Answering:** Answering questions posed about the image.

### Applications
Image processing has become an indispensable tool in a wide range of fields, transforming the way we interact with visual information and enabling innovative solutions to complex problems. Here are some key application areas:

#### Computer Vision
* **Object Recognition:** Identifying and classifying objects within images, enabling applications like automated product inspection, facial recognition, and self-driving cars.
* **Image Segmentation:** Partitioning an image into meaningful regions, used in medical imaging to identify organs or tumors, and in satellite imagery to classify land use.
* **Motion Analysis:** Tracking the movement of objects in video sequences, applied in surveillance systems, sports analysis, and human-computer interaction.

#### Medical Imaging
* **Disease Diagnosis:** Analyzing medical images (X-rays, MRI, CT scans) to detect abnormalities like tumors, fractures, and other medical conditions.
* **Image-guided Surgery:** Using image processing to assist surgeons during procedures, providing real-time visualization and guidance.
* **Microscopy and Cellular Imaging:** Enhancing and analyzing microscopic images to study cells, tissues, and microorganisms.

#### Remote Sensing
* **Environmental Monitoring:** Analyzing satellite and aerial images to monitor deforestation, pollution, and natural disasters.
* **Agriculture:** Assessing crop health, identifying diseases, and optimizing irrigation using aerial imagery.
* **Urban Planning:** Mapping urban areas, monitoring traffic flow, and planning infrastructure development.

#### Photography and Entertainment
* **Image Enhancement:** Improving the quality of photographs by adjusting contrast, sharpness, and color balance.
* **Special Effects:** Creating visual effects for movies and video games, such as adding objects, removing backgrounds, and generating realistic animations.
* **Image Restoration:** Removing noise, blur, and other artifacts from old or damaged photographs.

#### Security and Surveillance
* **Facial Recognition:** Identifying individuals for security and access control.
* **Object Detection:** Detecting suspicious objects or activities in surveillance footage.
* **Biometric Authentication:** Using fingerprints, iris scans, and other biometric traits for identification.

#### Industrial Automation
* **Quality Control:** Inspecting products for defects and ensuring quality standards.
* **Robot Vision:** Enabling robots to perceive and navigate their environment, used in manufacturing and assembly lines.
* **Optical Character Recognition (OCR):** Converting printed or handwritten text into digital format.

#### Scientific Research
* **Astronomy:** Analyzing images from telescopes to study celestial objects and phenomena.
* **Microscopy:** Enhancing and analyzing microscopic images to study cells, tissues, and materials.
* **Particle Physics:** Tracking and identifying particles in high-energy physics experiments.

## Sparsity in Signal Processing: From Compression to Reconstruction
This section explores the powerful role of sparsity in modern signal processing. We'll see how many signals can be efficiently represented by a small number of non-zero coefficients in a suitable basis, a property that underpins both efficient compression and the solution of challenging inverse problems. This journey will take us from traditional sampling methods to the revolutionary concept of compressed sensing, highlighting how sparsity transforms the way we acquire, represent, and reconstruct signals.

### Understanding Sparsity
Sparsity is a fundamental concept that underpins many modern signal processing techniques. It describes the phenomenon where a signal can be efficiently represented by a small number of non-zero components. This section delves into the key aspects of sparsity and its significance.  

#### What is Sparsity?
* **Sparse Signals:** A signal is considered sparse if it can be accurately represented with a small number of non-zero coefficients in a suitable basis or dictionary. In other words, most of the information content is concentrated in a few key components, while the rest are negligible or zero.
* **Dictionaries and Atoms:** A dictionary is a collection of elementary signals, called atoms, which serve as building blocks for representing more complex signals. Mathematically, a dictionary $$\Psi = (\psi_n)^N_{n=1}$$ consists of atoms $\psi_n$, where each atom is a vector in the signal space.
* **Sparse Representation:** A sparse representation of a signal $f$ in a dictionary $\Psi$ is a linear combination of a few atoms: $$f \approx \Psi \mathbf{x} := \sum_{n=1}^N x_n \psi_n$$ where $\mathbf{x} = (x_n)_{n=1}^N$ are the coefficients, and most of the $x_n$ values are zero.

#### Why is Sparsity Important?
Sparsity plays a crucial role in various signal processing tasks due to its numerous benefits:

1. **Efficient Compression:** Sparse representations enable significant data reduction by storing only the essential non-zero coefficients and their locations. This is crucial for handling large datasets, especially in applications like image and video compression.
2. **Noise Reduction:** Sparsity aids in denoising because noise typically affects all coefficients, while the true signal information is concentrated in a few. By promoting sparsity, we can effectively separate the signal from noise.  
3. **Solving Inverse Problems:** Sparsity acts as a powerful prior in solving inverse problems, where the goal is to recover an unknown signal from incomplete or degraded measurements. By leveraging the assumption of sparsity, we can achieve accurate and stable reconstruction.
4. **Reduced Computational Complexity:** Processing sparse signals often requires fewer computations compared to dense signals. This can lead to significant speedups in algorithms and reduce the computational burden.

#### Visualizing Sparsity
To better grasp the concept of sparsity, consider the following example:

* **Dense Representation:** Imagine a digital image represented by pixel intensity values. In a dense representation, all pixels contribute to the image, even if some have very low values.
* **Sparse Representation:** Now, imagine representing the same image using a wavelet basis. In this case, many coefficients will be close to zero, indicating that only a few wavelets are needed to capture the essential features of the image.

This sparsity in the wavelet domain allows for efficient compression and manipulation of the image.

By understanding the principles of sparsity and its benefits, we can appreciate its transformative impact on various signal processing applications, from compression and denoising to solving complex inverse problems and enabling new technologies like compressed sensing.

### Traditional Sampling and its Limitations
Traditional sampling forms the foundation of digital signal processing. It's the process of converting a continuous signal into a discrete representation, enabling digital storage, transmission, and analysis. This section examines the traditional sampling process and its inherent limitations.

#### The Sampling Process
Continuous signals, such as audio waves or images, exist in the analog world. To process these signals using computers, we need to convert them into a digital format through sampling. This involves measuring the signal's amplitude at specific, regularly spaced intervals.  

* **Mathematical Representation:**
* Let $\tilde{f}(s)$ represent a continuous signal, where s is the independent variable (e.g., time or spatial coordinates).
* The sampling process generates a discrete signal $f = (f_q)_{q=1}^Q$, where each sample $f_q$ is obtained by integrating the continuous signal over a specific interval or region $c_q$: $$f_q = \int_{c_q} \tilde{f}(s) ds$$
* **Example:** In digital photography, the continuous scene is sampled by the camera sensor. Each pixel in the resulting image corresponds to a sample, integrating the light intensity over its area.  

#### Shannon-Nyquist Sampling Theorem
The Shannon-Nyquist sampling theorem provides a fundamental guideline for choosing the appropriate sampling rate to avoid information loss during digitization.  

* **The Theorem:** A continuous signal can be perfectly reconstructed from its samples if the sampling rate is at least twice the highest frequency present in the signal. This minimum rate is known as the Nyquist rate.
* **Implications:**
* **Undersampling:** If the sampling rate is below the Nyquist rate, high-frequency components will be aliased, leading to distortion in the reconstructed signal.
* **Oversampling:** Sampling above the Nyquist rate can improve the accuracy of reconstruction, but it increases the data volume and computational complexity.

#### Limitations of Traditional Sampling
While traditional sampling provides a faithful representation of a continuous signal, it has inherent limitations:

1. **Large Data Volume:** Sampling at or above the Nyquist rate often leads to large datasets, especially for signals with high bandwidths (e.g., high-resolution images, high-fidelity audio). This can strain storage and transmission resources.
2. **Uniform Sampling:** Traditional sampling typically uses uniform spacing between samples. This can be inefficient for signals that have non-uniform information content, where some regions may require denser sampling than others.
3. **Noisy Measurements:** In real-world scenarios, measurements are often corrupted by noise. Traditional sampling doesn't inherently address noise reduction, and additional processing steps are usually required.

These limitations motivate the exploration of alternative sampling and processing strategies, such as compressed sensing, which leverages sparsity to overcome some of these challenges.

### Nonlinear Approximation and Compression
Traditional signal processing often relies on linear methods, where signals are represented as weighted sums of basis functions (e.g., Fourier series). However, nonlinear approximation offers a powerful alternative, especially for signals exhibiting sparsity. This section explores how nonlinear approximation leverages sparsity for efficient signal compression.

#### Approximating with Sparse Representations
The goal of nonlinear approximation is to find the "best" representation of a signal using a limited number of components from a dictionary. Unlike linear methods that use all basis functions, nonlinear approximation selectively chooses the most relevant atoms.

* **Mathematical Formulation:** We aim to approximate a signal f using a linear combination of a few atoms from the dictionary $\Psi$: $$f \approx \Psi \mathbf{x} := \sum_{n=1}^N x_n \psi_n$$ where $\mathbf{x} = (x_n)^N_{n=1}$ are the coefficients representing the contribution of each atom.
* **Sparsity in Approximation:** To achieve compression, we seek a sparse representation where most of the coefficients $x_n$ are zero or close to zero. This means that only a small subset of atoms is actively contributing to the signal approximation.

#### Optimization for Sparse Approximation
Finding the sparsest representation that accurately approximates a signal leads to an optimization problem:

* The $\ell_0$ Minimization Problem: $$\mathbf{x}^* \in \mathop{\arg\min}_{\mathbf{x} \in \mathbb{R}^N} \{||f-\Psi \mathbf{x}||_2: ||\mathbf{x}||_0 \leq M\}$$ where:
* $||f-\Psi \mathbf{x}||_2$ quantifies the approximation error (typically using the Euclidean norm).
* $||\mathbf{x}||_0$ counts the number of non-zero coefficients in x (the "$\ell_0$ pseudo-norm").
* $M>0$ is the desired level of sparsity (number of non-zero coefficients).
* **Challenges:** Solving the $\ell_0$ minimization problem directly is generally NP-hard, meaning it's computationally very challenging, especially for high-dimensional signals.


#### Practical Solutions and Approximations
To address the computational challenges of $\ell_0$ minimization, several practical approaches are used:

1. **Greedy Algorithms:** These algorithms iteratively select atoms that best contribute to reducing the approximation error. Examples include Matching Pursuit and Orthogonal Matching Pursuit.
2. **$\ell_1$ Relaxation:** The $\ell_0$ norm is often replaced with the convex $\ell_1$ norm, leading to a more tractable optimization problem: $$\mathbf{x}^* \in \mathop{\arg\min}_{\mathbf{x} \in \mathbb{R}^N} \{||f-\Psi \mathbf{x}||_2 + \lambda ||\mathbf{x}||_1\}$$ where $\lambda>0$ is a regularization parameter that balances the approximation error and sparsity.
3. **Specialized Dictionaries:** Choosing dictionaries that are well-suited to the signal structure (e.g., wavelets for images, curvelets for edges) can significantly improve the efficiency of sparse approximation.

#### Impact on Compression
Nonlinear approximation, by finding sparse representations, enables efficient signal compression:

* **Reduced Storage:** Only the non-zero coefficients and their indices need to be stored, significantly reducing the data volume compared to storing all signal samples.
* Adaptive Compression: The level of sparsity (controlled by $M$ or $\lambda$) can be adjusted to achieve different compression ratios, trading off fidelity for storage space.

Nonlinear approximation and sparse representations form the cornerstone of many modern compression standards, such as JPEG 2000 for images, enabling efficient storage and transmission of large multimedia datasets.

### Sparsity in Inverse Problems
Inverse problems are ubiquitous in science and engineering, arising whenever we seek to infer underlying causes from observed effects. Examples range from image deblurring and medical imaging to seismic tomography and astronomical observations. This section examines how the concept of sparsity provides a powerful framework for tackling the challenges posed by inverse problems.

#### What are Inverse Problems?
In many real-world scenarios, the data we acquire is an indirect or degraded representation of the underlying phenomenon we wish to understand. Inverse problems involve recovering the original signal or information from these imperfect measurements.

* **Mathematical Formulation:** The process of signal acquisition and degradation can often be modeled as: $$\mathbf{y} = \Phi f + \mathbf{w}$$ where:
* $\mathbf{y} \in \mathbb{R}^P$ represents the observed or measured data.
* $\Phi: \mathbb{R}^Q \rightarrow \mathbb{R}^P$ is a linear operator (often a matrix) modeling the acquisition system or degradation process (e.g., blurring, projection).
* $f \in \mathbb{R}^Q$ is the original, unknown signal we aim to recover.
* $\mathbf{w} \in \mathbb{R}^P$ represents additive noise or errors in the measurement.
* **Examples:**
* **Image Deblurring:** $\Phi$ represents a convolution operator that models the blurring process, and we aim to recover the sharp image $f$ from the blurred observation $\mathbf{y}$.
* **Medical Imaging (CT scans):** $\Phi$ represents the Radon transform, which models the projection of a 3D object onto 2D X-ray images. The goal is to reconstruct the 3D object from its projections.
* **Denoising:** $\Phi$ is the identity matrix, and the problem reduces to removing noise $\mathbf{w}$ from the observed signal $\mathbf{y}$.

#### Challenges in Inverse Problems
Solving inverse problems is inherently challenging due to several factors:

1. **Ill-posedness:** The problem may not have a unique solution, or the solution may be extremely sensitive to small changes in the observed data. This makes the reconstruction process unstable.
2. **Noise Amplification:** Noise in the measurements can be amplified during the reconstruction process, especially when the operator $\Phi$ is ill-conditioned (having small singular values).
3. **Computational Complexity:** Solving inverse problems often involves large-scale optimization problems that can be computationally expensive.


#### Sparsity to the Rescue
Sparsity provides a powerful tool for overcoming these challenges. By assuming that the original signal $f$ has a sparse representation in a suitable basis $\Psi$ ($f \approx \Psi x$), we can incorporate this prior knowledge into the reconstruction process.

* **Sparse Regularization:** This leads to optimization problems of the form: $$\mathbf{x}^* \in \mathop{\arg\min}_{\mathbf{x} \in \mathbb{R}^N} \{||\mathbf{y} - \Phi \Psi \mathbf{x}||_2 + \lambda ||\mathbf{x}||_0 \}$$ where $||\mathbf{x}||_0$ encourages sparsity in the solution, and $\lambda>0$ is a regularization parameter balancing data fidelity and sparsity.
* $\ell_1$ Relaxation: Since the $\ell_0$ norm is non-convex and computationally intractable, it is often replaced with the convex $\ell_1$ norm: $$\mathbf{x}^* \in \mathop{\arg\min}_{\mathbf{x} \in \mathbb{R}^N} \{||\mathbf{y} - \Phi \Psi \mathbf{x}||_2 + \lambda ||\mathbf{x}||_1 \}$$ This $\ell_1$-regularized problem is computationally tractable and still promotes sparsity in the solution.

#### Benefits of Sparse Regularization
1. **Improved Stability:** Sparsity constraints help regularize the inverse problem, making the solution less sensitive to noise and reducing ill-posedness.
2. **Accurate Reconstruction:** By leveraging the sparsity prior, we can achieve accurate reconstruction even from limited or noisy measurements.
3. **Feature Selection:** In some applications, the sparse representation can highlight the most important features or components of the underlying signal.

Sparsity-based techniques have revolutionized the field of inverse problems, enabling significant advances in medical imaging, image processing, and other areas where recovering information from indirect measurements is crucial.

### Compressed Sensing: A Paradigm Shift
Compressed sensing (CS) is a revolutionary paradigm in signal processing that challenges the traditional Shannon-Nyquist sampling theorem. It leverages the fact that many signals of interest are sparse or compressible to acquire and compress data simultaneously, significantly reducing the number of measurements required for accurate reconstruction.

#### The Core Idea
Traditional sampling requires a high sampling rate to capture all the information in a signal, leading to large datasets. Compressed sensing, on the other hand, exploits sparsity to acquire far fewer measurements than dictated by the Nyquist rate, while still guaranteeing accurate reconstruction.  

* **Breaking the Nyquist Barrier:** CS demonstrates that it's possible to reconstruct a signal from far fewer samples than traditionally thought necessary, as long as the signal is sparse in some domain.
* **Simultaneous Sensing and Compression:** CS performs sensing and compression simultaneously, reducing the data acquisition burden and storage requirements. This is particularly beneficial in applications where acquiring measurements is expensive or time-consuming.  

#### Key Principles
Compressed sensing relies on two fundamental principles:

1. **Sparsity:** The signal of interest must have a sparse representation in some basis or dictionary. This means it can be accurately represented by a small number of non-zero coefficients.
2. **Incoherence:** The measurement process should be incoherent with the sparsity basis. This means the measurements should spread the information content of the signal across many coefficients, effectively capturing its essential features. This is often achieved using random measurement matrices.

#### The Single-Pixel Camera: A Practical Example
The single-pixel camera is a compelling illustration of compressed sensing in action. It captures images using a single photodiode and a digital micromirror device (DMD).  


* **Measurement Process:**
* The DMD consists of an array of tiny mirrors that can be individually tilted to reflect or absorb light.  
* For each measurement, the DMD is configured with a random pattern of mirror orientations.  
* The single photodiode measures the total intensity of light reflected from the DMD.  
* By repeating this process with different random patterns, a series of measurements is obtained, encoding the image information.
* **Mathematical Representation:** $$\mathbf{y} = \sum_q \Phi_{q} \int_{c_q} \tilde{f}(s) ds + \mathbf{w} = (\Phi f) + \mathbf{w}$$ where:
* $\mathbf{y} \in \mathbb{R}^P$ is the vector of measurements ($P$ is the number of measurements, much smaller than the number of pixels).
* $\Phi \in \mathbb{R}^{P \times Q}$ is the measurement matrix, where each row represents a DMD pattern.
* $f \in \mathbb{R}^Q$ is the vectorized image to be reconstructed ($Q$ is the number of pixels).
* $\mathbf{w} \in \mathbb{R}^P$ is the measurement noise.

#### Reconstruction from Compressed Measurements
Recovering the original signal $f$ from the compressed measurements $\mathbf{y}$ involves solving an underdetermined linear system ($P<<Q$). This is achieved by leveraging the sparsity prior and optimization techniques.

* **Optimization Problem:** $$\mathbf{x}^* = \mathop{\arg\min} ||\mathbf{x}||_1 \text{ subject to } ||\mathbf{y} - \Phi \Psi \mathbf{x}||_2 \leq \epsilon$$ where
* $\mathbf{x}$ is the sparse representation of the signal
* $||\mathbf{x}||_1$ promotes sparsity
* $||\mathbf{y} - \Phi \Psi \mathbf{x}||_2$ ensures fidelity to the measurements,
* $\epsilon$ accounts for noise.
* **Reconstruction Algorithms:** Various algorithms, such as basis pursuit, matching pursuit, and iterative thresholding, are used to solve this optimization problem and recover the sparse signal.

#### Theoretical Guarantees
Compressed sensing theory provides remarkable guarantees for accurate signal reconstruction under certain conditions:

1. **Restricted Isometry Property (RIP):** The measurement matrix $\Phi$ should satisfy the RIP, which essentially ensures that it preserves the distances between sparse vectors.
2. **Number of Measurements:** The number of measurements $P$ needs to be sufficiently large, typically scaling logarithmically with the sparsity level of the signal.

If these conditions are met, with high probability, the solution to the optimization problem will yield an accurate reconstruction.

#### Impact and Applications
Compressed sensing has profound implications for various fields:

1. **Medical Imaging:** Reducing scan times and radiation exposure in MRI and CT scans.
2. **Remote Sensing:** Efficient transmission of data from satellites and other remote sensors. 
3. **Signal Processing:** Enabling new approaches to signal acquisition, compression, and analysis in areas like communications, radar, and image processing.  

Compressed sensing represents a paradigm shift by demonstrating that efficient signal acquisition is possible with far fewer measurements than previously thought, opening up new possibilities in various domains.  

## Wavelets
Wavelets are mathematical functions that cut up data into different frequency components, then study each component with a resolution matched to its scale. Imagine them as a powerful microscope that can zoom in and out to reveal both the fine details and the overall structure of a signal. This ability to analyze information at multiple scales sets wavelets apart from traditional Fourier analysis, which provides a global frequency perspective but can miss localized events.

Why are wavelets so useful? Think of analyzing a piece of music. Fourier analysis would tell you the notes being played, but not when they occur. Wavelets, on the other hand, reveal both the notes and their timing, like a musical score. This makes them ideal for analyzing signals with:

* **Sharp changes:** Like a sudden drumbeat in music or a spike in stock market data.
* **Transient features:** Think of a brief chirp in a bird song or a glitch in a machine's operation.
* **Varying frequency content:** Such as a piece of music that transitions from slow, low notes to fast, high notes.

Wavelets come in various "flavors," each with its own shape and properties. Some common types include:

* **Haar wavelets:** The simplest type, resembling a step function.
* **Daubechies wavelets:** Offer a balance of smoothness and localization.
* **Symlets:** Nearly symmetrical, useful for certain applications.


### Background
Before diving into the specifics of wavelets, it's helpful to understand the concepts that paved the way for their development. This section explores the foundational ideas of Fourier analysis and dilation, providing context for the emergence of wavelets.

#### Fourier Analysis: A Starting Point
For centuries, Fourier analysis has been the cornerstone of signal processing. Developed by Joseph Fourier in the 19th century, it decomposes a signal into a sum of sine and cosine waves of different frequencies. Think of it like separating white light into a rainbow of colors, where each color represents a specific frequency.

* **Fourier Series:** Used for periodic signals (those that repeat regularly), like a heartbeat or a musical note. $$f(x) = a_0 + \sum_{k=1}^{\infty} \left[a_k \cos(kx) + b_k \sin(kx) \right]$$
* **Fourier Transform:** Extends the concept to non-periodic signals, like speech or a seismic wave $$F(\omega) = \int^{\infty}_{-\infty} f(t) e^{-i \omega t} dt$$


While powerful, Fourier analysis has limitations. It excels at revealing the global frequency content of a signal, but struggles to pinpoint when those frequencies occur. Imagine trying to analyze a bird's song using only Fourier analysis – you'd know the frequencies present but not the timing of the chirps and trills. This is where wavelets come in.

#### Dilation: The Essence of Scale
Dilation is a core concept in wavelet theory. It refers to the stretching or compressing of a function. Think of zooming in or out on a map – you're essentially dilating the map to see finer details or a broader view.


In the context of wavelets, dilation equations play a crucial role. These equations define a function in terms of scaled and shifted copies of itself. This self-similarity across scales is what allows wavelets to analyze signals at multiple resolutions.

##### Why is dilation important?
* **Analyzing localized features:** By dilating a wavelet, we can adjust its "window" to focus on specific parts of a signal.
* **Multiresolution analysis:** We can analyze a signal at various scales, from coarse overall trends to fine details.

By understanding dilation, we can grasp how wavelets are generated and how they capture information across different scales, providing a more complete picture than Fourier analysis alone.

### Wavelet Systems and Construction
A wavelet system is like a toolbox equipped with specialized functions for analyzing signals at different scales. The foundation of this toolbox is the **scaling function**, denoted by $\phi(x)$. This function is the solution to a dilation equation, which, as we saw with the Haar wavelet, expresses the function in terms of scaled and shifted copies of itself.

#### The Dilation Equation
The foundation of a wavelet system is the scaling function, denoted by $\phi(x)$. This function is not arbitrary; it's a solution to a specific dilation equation, which expresses the scaling function in terms of scaled and shifted copies of itself:

$$
\phi(x) = \sum_{k=0}^{d-1} c_k \phi(2x-k)
$$

This equation might seem a bit abstract, but it's the key to generating a family of functions that can analyze signals at multiple resolutions. The coefficients $c_k$ are the building blocks of the wavelet system, determining the properties of the resulting wavelets, such as their smoothness, support (the region where the function is non-zero), and ability to represent various signal characteristics.

##### Understanding the Dilation Equation
* **Scaling:** The term $\phi(2x)$ represents a compressed version of the scaling function.
* **Shifting:** The term $\phi(2x−k)$ shifts the compressed function by $k$ units.
* **Linear Combination:** The equation states that the scaling function is a weighted sum of these compressed and shifted versions.

#### The Haar Wavelet: A Concrete Example
Let's illustrate this with the Haar wavelet, the simplest example of a wavelet system. Its scaling function, a basic box function, is defined by the dilation equation:

$$
\phi(x) = \phi(2x) + \phi(2x-1)
$$

This equation shows that the Haar scaling function is the sum of two compressed and shifted copies of itself. This simplicity makes it an excellent starting point for understanding wavelet construction.


#### Scaling and Wavelet Functions: A Complementary Pair
While the scaling function provides a coarse approximation of a signal, it's like viewing a blurry image. To capture the finer details, the sharp edges, and sudden changes, we need its counterpart: the **wavelet function**, denoted by $\psi(x)$.

The wavelet function is also derived from the scaling function, but it's specifically designed to capture the "high-frequency" information that the scaling function misses. The mother wavelet, $\psi(x)$, is defined as a linear combination of scaled and shifted scaling functions:

$$
\psi(x) = \sum_{k=0}^{d-1} b_k \phi(2x-k)
$$

The coefficients $b_k$ are intricately related to the $c_k$ from the dilation equation and are chosen to ensure orthogonality between the wavelet and scaling functions. This relationship is often expressed as:

$$
b_k = (-1)^k c_{d-1-k}
$$

This ensures that the wavelet function captures the details that the scaling function overlooks, providing a complete picture of the signal.

#### Iterative Construction: A Refinement Process
Finding the scaling function that satisfies the dilation equation can be challenging. For complex dilation equations, where a closed-form solution is elusive, an iterative approach is employed. This involves:

1. **Starting with an initial guess:** Begin with a simple function, $\phi_0(x)$, as an approximation of the scaling function.
2. **Repeatedly applying the dilation equation:** Plug the current approximation, $\phi_n(x)$, into the dilation equation to obtain a refined approximation, $\phi_{n+1}(x)$: $$\phi_{n+1}(x) = \sum_{k=0}^{d-1} c_k \phi_n(2x - k)$$
3. **Iterating until convergence:** Repeat this process until the approximation converges to a stable function, $\phi(x)$. Convergence is often assessed by analyzing the eigenvalues of a matrix derived from the coefficients $c_k$. If the magnitude of all eigenvalues, except for a single eigenvalue of 1, are less than 1, the iteration will converge.

This iterative process gradually refines the initial guess, molding it into the desired scaling function.

#### Conditions for Orthogonality: Ensuring Efficiency and Completeness
Orthogonality is a crucial property in wavelet systems. It ensures that the scaling and wavelet functions at different scales and shifts are "independent" of each other, like puzzle pieces that fit together perfectly without overlap. This is essential because:

* **It avoids redundancy:** We can decompose a signal into its wavelet components without unnecessary information, leading to efficient signal representation.
* **It enables perfect reconstruction:** We can recover the original signal exactly from its wavelet components.

To achieve orthogonality, specific conditions are imposed on the coefficients $c_k$ and $b_k$ in the dilation equations. These conditions guarantee that the resulting wavelet system forms an orthonormal basis.

**Conditions on the scaling function coefficients:**
* **Non-zero integral:** To ensure the scaling function can represent constant functions, its integral must be non-zero: $$\int^{\infty}_{-\infty} \phi(x) dx \neq 0$$ This translates to a constraint on the coefficients: $$\sum_{k=0}^{d-1} c_k = 2$$
* **Orthogonality of integer shifts:** To guarantee orthogonality between integer shifts of the scaling function: $$\int^{\infty}_{-\infty} \phi(x) \phi(x-l) dx = \delta(l)$$ where $\delta(l)$ is the Kronecker delta, which is 1 when $l=0$ and 0 otherwise. This condition leads to another constraint on the coefficients: $$\sum_{i=0}^{d-1} c_i c_{i-2l} = 2 \delta(l)$$

**Conditions on the wavelet function coefficients:**
* **Orthogonality to the scaling function:** The wavelet function must be orthogonal to the scaling function: $$\int^{\infty}_{-\infty} \phi(x) \psi(x-l) dx = 0$$
* **Orthogonality of integer shifts:** Similar to the scaling function, integer shifts of the wavelet function must be orthogonal to each other: $$\int^{\infty}_{-\infty} \psi(x) \psi(x-l) dx = \delta(l)$$

These conditions, when combined with the relationship between $b_k$ and $c_k$, ensure that the wavelet system forms an orthonormal basis, a powerful tool for signal analysis and processing.

### Working with Wavelets
Now that we've laid the mathematical groundwork, let's explore how to actually use wavelets to analyze and process signals. This involves understanding the wavelet transform, multiresolution analysis, and how to choose the right wavelet for the job.

#### The Wavelet Transform: A Multiscale Lens
The wavelet transform is the process of decomposing a signal into its wavelet components at different scales and positions. It's like viewing a signal through a special lens that can zoom in and out, revealing both the big picture and the fine details.

There are two main types of wavelet transforms:

* **Continuous Wavelet Transform (CWT):** This provides a highly detailed view of the signal, analyzing it at every possible scale and position. It's like continuously zooming in and out and panning across the signal. This results in a redundant representation, but it's useful for analyzing signals with complex and non-stationary features, where the frequency content changes over time.
* **Discrete Wavelet Transform (DWT):** This is a more computationally efficient approach, analyzing the signal at discrete scales and positions, typically at dyadic scales (powers of 2). It's like viewing the signal at specific zoom levels. The DWT is widely used in applications like image compression and denoising, where computational efficiency is important.

Intuitively, the wavelet transform involves:

1. **Choosing a mother wavelet:** Select a wavelet function that suits the characteristics of the signal.
2. **Scaling and shifting:** Create a family of wavelets by scaling and shifting the mother wavelet.
3. **Calculating coefficients:** Compute the inner product of the signal with each wavelet in the family. These inner products represent how much the signal "resembles" each wavelet at different scales and positions.

#### Multiresolution Analysis (MRA): A Hierarchical View
Multiresolution analysis (MRA) provides a framework for analyzing signals at multiple resolutions. It's like organizing a signal into a hierarchy of details, from coarse approximations to fine nuances.

MRA utilizes the nested spaces spanned by the scaling functions at different scales. This allows us to decompose a signal into:

* **A coarse approximation:** A low-resolution representation of the signal, capturing its overall trend.
* **Detail signals:** A series of signals capturing the details lost at each level of approximation.

This decomposition is typically achieved by passing the signal through a series of high-pass and low-pass filters associated with the wavelet system. The high-pass filter extracts the detail information, while the low-pass filter captures the coarse approximation.

The power of MRA lies in its ability to:

* **Isolate features at different scales:** We can separate the large-scale trends from the small-scale fluctuations.
* **Efficiently represent signals:** We can often represent a signal accurately using a small number of wavelet coefficients, leading to compression.
* **Analyze non-stationary signals:** We can track how the frequency content of a signal changes over time.

#### Choosing a Wavelet System: Finding the Right Tool
The choice of wavelet system depends on the specific application and the characteristics of the signal being analyzed. Here's a brief overview of some common wavelet families:

| Wavelet Family | Characteristics | Applications |
|----------------|-----------------|--------------|
| Haar | Simple, computationally efficient, but not very smooth | Educational examples, basic signal processing |
| Daubechies | Good balance of smoothness and localization | Image compression, denoising |
| Symlets | Nearly symmetrical, good for linear phase filters | Signal processing, numerical analysis |
| Coiflets | More vanishing moments, good for representing smooth signals | Signal analysis, feature extraction |
| Biorthogonal | Use different wavelets for decomposition and reconstruction, offer more flexibility | Image processing, biomedical signal processing |


**Factors to consider when choosing a wavelet:**
* **Signal characteristics:** Is the signal smooth or discontinuous? Does it have sharp transitions?
* **Application requirements:** What is the goal of the analysis? Compression? Denoising? Feature extraction?
* **Computational resources:** How much processing power is available?

### Applications of Wavelets
Wavelets have emerged as a versatile tool with applications spanning a wide range of fields. Their ability to analyze signals with both frequency and spatial precision makes them particularly well-suited for tasks where traditional Fourier methods fall short. Let's explore some key areas where wavelets are making a significant impact.

#### Signal and Image Processing
* **Image Compression:** Wavelets excel at compressing images by efficiently representing them using a small number of wavelet coefficients. This is because many images have a sparse representation in the wavelet domain, meaning only a few coefficients are needed to capture the essential information. This sparsity leads to high compression ratios without significant loss of quality. **JPEG 2000**, a widely used image compression standard, utilizes wavelet transforms for its superior compression algorithm.
* **Denoising:** Wavelet transforms can effectively separate noise from signals. By thresholding or shrinking the wavelet coefficients, noise can be attenuated while preserving the important features of the signal. This is crucial in applications like medical imaging, where noise can obscure critical diagnostic information, and audio processing, where noise reduction can significantly improve sound quality.
* **Feature Extraction:** Wavelets can be used to extract relevant features from signals and images. For instance, in image analysis, wavelets can detect edges, corners, and other salient features, which are crucial for object recognition, image segmentation, and image understanding.

#### Computer Vision
* **Object Recognition:** Wavelet-based features can be used to represent objects in images, enabling efficient and robust object recognition algorithms. The spatial localization of wavelets allows for robust recognition even when objects are partially occluded or distorted.
* **Image Segmentation:** Wavelets can be used to segment images into meaningful regions, separating objects from the background or identifying different textures within an image. By analyzing the wavelet coefficients at different scales, boundaries between objects can be identified.
* **Texture Analysis:** Wavelets are effective at characterizing textures in images. The distribution of wavelet coefficients across different scales and orientations provides valuable information about the texture properties, such as coarseness, directionality, and regularity.

#### Communications
* **Power Line Communication:** Wavelets are used in power line communication protocols to transmit data over power lines, which are typically noisy channels. Wavelets' ability to handle noise and their efficient representation of signals make them suitable for this challenging communication environment.
* **Wireless Communication:** Wavelet-based modulation techniques are used in wireless communication systems to improve spectral efficiency and robustness to interference. By encoding information in the wavelet coefficients, these techniques can achieve higher data rates and better performance in noisy wireless environments.

#### Other Applications
* **Biomedical Signal Processing:** Wavelets are used to analyze biomedical signals like ECG (electrocardiogram) and EEG (electroencephalogram) for diagnostic purposes. They can help detect abnormalities, such as heart arrhythmias or brain seizures, by identifying specific patterns in the wavelet coefficients.
* **Financial Modeling:** Wavelets are used to model stock market data and predict market trends. They can capture the volatility and non-stationary behavior of financial time series, allowing for more accurate forecasting and risk management.
* **Geophysics:** Wavelets are used to analyze seismic data for oil and gas exploration. They can help identify geological structures and potential hydrocarbon reservoirs by analyzing the reflections and refractions of seismic waves.
* **Numerical Analysis:** Wavelets are used to solve differential equations and perform numerical simulations. Their ability to represent functions at multiple scales makes them efficient for solving problems with localized features or sharp transitions.

The versatility of wavelets stems from their ability to provide a multiresolution view of signals, capturing both frequency and spatial information. This makes them a powerful tool for a wide range of applications, and their impact continues to grow as researchers explore new ways to leverage their capabilities.

## Reference
* Graps, A. (1995). An Introduction to Wavelets. IEEE Computational Science and Engineering, 2(2), 50-61. https://doi.org/10.1109/99.388960
* Peyré, G. (2018). An Introduction to Data Sciences, Chapters 1-3. [link](https://mathematical-tours.github.io/book-basics/)
* Peyré, G. (2024). Mathematical Foundations of Data Sciences, Chapters 1-10. [link](https://mathematical-tours.github.io/book/)
* Numerical Tours in Python: https://www.numerical-tours.com/python/
* Blum, A., Hopcroft, J., & Kannan, R. (2020). Foundations of Data Science. Cambridge University Press, Chapter 11

## Further Reading
### Information Theory
* Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (2nd ed.). Wiley. https://doi.org/10.1002/047174882X
* MacKay, D. J. C. (2003). Information Theory, Inference and Learning Algorithms. Cambridge University Press.

### Signal Processing
* Foucart, S., & Rauhut, H. (2013). A mathematical introduction to compressive sensing (Applied and Numerical Harmonic Analysis). Birkhäuser Basel. https://doi.org/10.1007/978-0-8176-4948-7
* Mallat, S. (2009). A Wavelet Tour of Signal Processing: The Sparse Way (3rd ed.). Academic Press.