Compressed Sensing in Information Processing

ANHA Series Preface
Preface
Acknowledgements
Contents
Contributors
1 Hierarchical Compressed Sensing
1.1 Introduction
1.2 Hierarchically Sparse Vectors
1.3 Hierarchical Thresholding and Recovery Algorithms
1.4 Hierarchically Restricted Isometric Measurements
1.4.1 Gaussian Operators
1.4.2 Coherence Measures
1.4.3 Hierarchical Measurement Operators
1.5 Sparse De-mixing of Low-Rank Matrices
1.6 Selected Applications
1.6.1 Channel Estimation in Mobile Communication
1.6.2 Secure Massive Access
1.6.3 Blind Quantum State Tomography
1.7 Conclusion and Outlook
References
2 Proof Methods for Robust Low-Rank Matrix Recovery
2.1 Introduction
2.1.1 Sample Applications
2.1.1.1 Matrix Completion
2.1.1.2 Blind Deconvolution
2.1.1.3 Phase Retrieval
2.1.2 This Work
2.2 Recovery Guarantees via a Descent Cone Analysis
2.2.1 Descent Cone Analysis
2.2.2 Application 1: Generic Low-Rank Matrix Recovery
2.2.3 Application 2: Phase Retrieval
2.2.4 Limitations
2.3 Recovery Guarantees via the Golfing Scheme
2.3.1 Recovery Guarantees via Dual Certificates
2.3.2 Golfing with Precision
2.3.3 Application 3: Matrix Completion
2.3.4 Application 4: Simultaneous Demixing and Blind Deconvolution
2.3.5 Phase Retrieval with Incoherence
2.4 More Refined Descent Cone Analysis
2.4.1 Application 5: Blind Deconvolution
2.4.2 Application 6: Phase Retrieval with Incoherence
2.5 Conclusion
Appendix: Descent Cone Elements Are Effectively Low Rank
References
3 New Challenges in Covariance Estimation: Multiple Structures and Coarse Quantization
3.1 Introduction
3.1.1 Outline and Notation
3.2 Motivation: Massive MIMO
3.3 Estimation of Structured Covariance Matrices and Robustness Against Outliers
3.3.1 Sparse Covariance Matrices
3.3.2 Low-Rank Covariance Matrices
3.3.3 Toeplitz Covariance Matrices and Combined Structures
3.4 Estimation from Quantized Samples
3.4.1 Sign Quantization
3.4.2 Dithered Quantization
3.5 The Underlying Structures of Massive MIMO Covariance Estimation
3.6 Conclusion
Appendix: Proof of Theorem 3.6
References
4 Sparse Deterministic and Stochastic Channels: Identification of Spreading Functions and Covariances
4.1 Motivation and Introduction
4.2 Channel Identification and Estimation
4.2.1 Time–Frequency Analysis in Finite Dimensions
4.2.2 Deterministic Channels
4.2.3 Stochastic Channels
4.3 Results in Deterministic Setting
4.3.1 Classical Results on Channel Identification
4.3.1.1 Identification of SISO Channels
4.3.1.2 Identification of MIMO Channels
4.3.2 Linear Constraints
4.3.3 Message Transmission Using Unidentified Channels
4.3.3.1 Problem Formulation
4.3.3.2 Message Transmission with Known Support
4.3.3.3 Message Transmission with Unknown Support
4.4 Results in Stochastic Setting
4.4.1 Permissible and Defective Support Patterns
4.4.2 Linear Constraints in Stochastic Setting
4.4.2.1 WSSUS Pattern with Additional Off-diagonal Contributions
4.4.2.2 Tensor Product Pattern with Additional Contributions
4.4.3 Numerical Simulations
Appendix
Proof of Lemma 4.3
Proof of Proposition 4.6
Proof of Proposition 4.7
Proof of Proposition 4.8
Proof of Proposition 4.10
Proof of Proposition 4.11
References
5 Analysis of Sparse Recovery Algorithms via the Replica Method
5.1 Introduction
5.2 A Multi-terminal Setting for Compressive Sensing
5.2.1 Characterization of the Recovery Performance
5.2.2 Stochastic Model of System Components
5.2.3 Stochastic Model for Jointly Sparse Signals
5.2.4 Special Cases
5.2.4.1 Classical Compressive Sensing
5.2.4.2 Multiple Measurement Vectors
5.2.4.3 Distributed Compressive Sensing
5.3 Sparse Recovery via the Regularized Least-Squares Method
5.3.1 Some Well-Known Forms
5.3.1.1 p-Norm Minimization
5.3.1.2 p,q-Norm Minimization
5.3.2 Bayesian Interpretation
5.4 Asymptotic Characterization
5.4.1 Stieltjes and R-Transforms
5.5 Building a Bridge to Statistical Mechanics
5.5.1 Introduction to Statistical Mechanics
5.5.1.1 Second Law of Thermodynamics
5.5.1.2 Spin Glasses
5.5.1.3 Thermodynamic Limit
5.5.1.4 Averaging Trick
5.5.2 Corresponding Spin Glass
5.5.2.1 Asymptotic Distortion as a Macroscopic Parameter
5.5.3 The Replica Method
5.6 The Replica Analysis
5.6.1 General Form of the Solution
5.6.2 Constructing Parameterized Qj
5.6.2.1 Replica Symmetric Solution
5.6.2.2 Replica Symmetry Breaking
5.7 Applications and Numerical Results
5.7.1 Performance Analysis of Sparse Recovery
5.7.2 Tuning RLS-Based Algorithms
5.8 Summary and Final Discussions
5.8.1 Decoupling Principle
5.8.2 Nonuniform Sparsity Patterns
5.8.3 Extensions to Bayesian Estimation
5.9 Bibliographical Notes
References
6 Unbiasing in Iterative Reconstruction Algorithms for Discrete Compressed Sensing
6.1 Introduction
6.1.1 Compressed Sensing Problem and Reconstruction Algorithms
6.1.2 Discrete Setting
6.1.3 Outline of the Chapter
6.2 Problem Statement and Iterative Algorithms
6.2.1 Factorization and Message-Passing Approaches
6.2.1.1 Message-Passing Approaches
6.2.1.2 Partitioning of the Problem
6.2.2 Exponential Families
6.3 Expectation-Consistent Approximate Inference
6.3.1 Derivation and Optimization Procedure
6.3.2 Algorithms
6.3.2.1 Optimization: ECopts, ECoptc and ECseqs, ECseqc
6.3.2.2 Vector Approximate Message Passing: VAMP
6.3.2.3 Discussion
6.3.3 Alternative Partitioning of the Problem
6.4 Unbiasing of MMSE Estimators
6.4.1 Joint Linear Estimators
6.4.1.1 Average Unbiasing
6.4.1.2 Individual Unbiasing
6.4.2 Scalar Non-linear Estimators
6.4.2.1 Signal-Oriented Unbiasing
6.4.2.2 Noise-Oriented Unbiasing
6.4.3 Iterative Schemes with Individual and Average Variances
6.5 Numerical Results and Discussion
6.5.1 Average Variance
6.5.2 Individual Variances
References
7 Recovery Under Side Constraints
7.1 Introduction
7.2 Sparse Recovery in Sensor Arrays
7.2.1 Compressive Data Model for Sensor Arrays
7.2.2 Sparse Recovery Formulations for Sensor Arrays
7.3 Recovery Guarantees Under Side Constraints
7.3.1 Integrality Constraints
7.3.2 General Framework for Arbitrary Side Constraints
7.4 Recovery Algorithms Under Different Side Constraints for the Linear Measurement Model
7.4.1 Constant-Modulus Constraints
7.4.2 Row- and Rank-Sparsity
7.4.3 Block-Sparse Tensors
7.4.4 Non-circularity
7.5 Mixing Matrix Design
7.5.1 Sensing Matrix Design: P = M Case
7.5.2 Sensing Matrix Design: The General Case
7.5.3 Numerical Results
7.6 Recovery Algorithms for the Nonlinear Measurement Model
7.6.1 Sparse Phase Retrieval
7.6.2 Phase Retrieval with Dictionary Learning
7.7 Conclusions
References
8 Compressive Sensing and Neural Networks from a Statistical Learning Perspective
8.1 Introduction
8.1.1 Notation
8.2 Deep Learning and Inverse Problems
8.2.1 Learned Iterative Soft Thresholding
8.2.2 Variants of LISTA
8.3 Generalization of Deep Neural Networks
8.3.1 Rademacher Complexity Analysis
8.3.2 Generalization Bounds for Deep Neural Networks
8.4 Generalization of Deep Thresholding Networks
8.4.1 Boundedness: Assumptions and Results
8.4.2 Dudley's Inequality
8.4.3 Bounding the Rademacher Complexity
8.4.4 A Perturbation Result
8.4.5 Covering number estimates
8.4.6 Main result
8.5 Thresholding Networks for Sparse Recovery
8.6 Conclusion and Outlook
References
9 Angular Scattering Function Estimation Using Deep Neural Networks
9.1 Introduction
9.1.1 Related Work
9.1.2 Outline and Notation
9.2 System Model
9.3 The Parametric Form of ASF
9.3.1 The Continuous ASF Component
9.3.2 The Discrete ASF Component
9.4 Pre-processing: Discrete AoA Estimation via MUSIC
9.5 A Deep Learning Approach to ASF Estimation
9.5.1 Training Phase
9.5.2 Network Architecture
9.5.3 Test Phase
9.6 Simulation Results
9.6.1 Metrics for Comparison
9.6.2 Performance with Different SNRs
9.6.3 Performance with Different Sample Numbers
9.7 Conclusion
References
10 Fast Radio Propagation Prediction with Deep Learning
10.1 Introduction
10.1.1 Applications of Radio Maps
10.1.2 Radio Map Prediction
10.1.3 Radio Map Prediction Using Deep Learning
10.2 Introduction to Radio Map Prediction with RadioUNet
10.2.1 RadioUNet Methods
10.2.2 The Training Data
10.2.3 Generalizing What Was Learned to Real-Life Scenarios
10.2.4 Applications
10.3 Background and Preliminaries
10.3.1 Wireless Communication
10.3.2 Deep Learning
10.3.2.1 An Interpretation of Deep Learning
10.3.2.2 Convolutional Neural Networks
10.3.2.3 UNets
10.3.2.4 Supervised Learning of UNets via Stochastic Gradient Descent
10.3.2.5 Curriculum Learning
10.3.2.6 Out-of-Domain Generalization
10.4 The RadioMapSeer Dataset
10.4.1 General Setting
10.4.1.1 Maps and Transmitters
10.4.1.2 Coarsely Simulated Radio Maps
10.4.1.3 Higher-Accuracy Simulations
10.4.1.4 Pathloss Scale
10.4.2 System Parameters
10.4.3 Gray-Level Conversion
10.5 Estimating Radio Maps via RadioUNets
10.5.1 Motivation for RadioUNet
10.5.2 Different Settings in Radio Map Estimation
10.5.2.1 Network Input Scenarios
10.5.2.2 Learning Scenarios
10.5.3 RadioUNet Architectures
10.5.3.1 Retrospective Improvement
10.5.3.2 Adaptation to Real Measurements
10.5.3.3 Thresholder
10.5.4 Training
10.5.5 RadioUNet Performance
10.6 Comparison of RadioUNet to State of the Art
10.6.1 Comparison to Model-Based Simulation
10.6.2 Comparison to Data-Driven Interpolation
10.6.3 Comparison to Model-Based Data Fitting
10.6.4 Comparison to Deep Learning Data Fitting
10.7 Applications
10.7.1 Coverage Classification
10.7.2 Pathloss-Based Fingerprint Localization
10.8 Conclusion
References
11 Active Channel Sparsification: Realizing Frequency-Division Duplexing Massive MIMO with Minimal Overhead
11.1 Introduction
11.2 System Model
11.2.1 Related Work
11.2.2 Contribution
11.3 Channel Model
11.4 Active Channel Sparsification and DL Channel Training
11.4.1 Necessity and Implication of Stable Channel Estimation
11.4.2 Sparsifying Precoder Design
11.4.3 Channel Estimation and Multiuser Precoding
11.5 Simulation Results
11.5.1 Channel Estimation Error and Sum Rate vs. Pilot Dimension
11.5.2 The Effect of Channel Sparsity
11.6 Beam-Space Design for Arbitrary Array Geometries
11.6.1 Jointly Diagonalizable Covariances
11.6.2 ML via Projected Gradient Descent
11.6.3 Extension of ACS to Arbitrary Array Geometries
References
12 Atmospheric Radar Imaging Improvements Using Compressed Sensing and MIMO
12.1 Introduction
12.2 System Model and Inversion Methods for Atmospheric Radar Imaging
12.2.1 System Model for SIMO Atmospheric Radar Imaging
12.2.2 System Model for MIMO Atmospheric Radar Imaging
12.2.3 SIMO vs MIMO Arrays
12.2.4 Inversion Methods
12.2.4.1 The Capon Method
12.2.4.2 Maximum Entropy Method
12.2.4.3 Compressed Sensing
12.2.5 MIMO Implementations
12.2.5.1 Time Diversity
12.2.5.2 Waveform Diversity
12.2.5.3 Suboptimal Diversity
12.3 Applications of MIMO in Atmospheric Radar Imaging
12.3.1 MIMO in Atmospheric Radar Imaging for Ionospheric Studies
12.3.2 Polar Mesospheric Summer Echoes Imaging
12.3.3 MIMO in Specular Meteor Radars to Measure Mesospheric Winds
12.4 Summary and Future Work
Table of Mathematical Symbols
References
13 Over-the-Air Computation for Distributed Machine Learning and Consensus in Large Wireless Networks
13.1 Introduction
13.2 Over-the-Air Computation
13.2.1 Digital Over-the-Air Computation
13.2.2 Analog Over-the-Air Computation
13.2.3 Analog Over-the-Air Computation as a Compressed Sensing Problem
13.3 Applications of Over-the-Air Computation
13.3.1 Distributed Machine Learning
13.3.2 Consensus Over Wireless Channels
13.3.3 Compressed Sensing
13.4 Distributed Function Approximation in Wireless Channels
13.4.1 Class of Functions
13.4.2 System and Channel Model
13.4.3 The Case of Independent Fading and Noise
13.4.4 The Case of Correlated Fading and Noise
13.5 DFA Applications to VFL
13.6 Security in OTA Computation
13.6.1 Information-Theoretic Preliminaries
13.6.2 Result and Discussion
13.7 Open Research Questions
References
14 Information Theory and Recovery Algorithms for Data Fusion in Earth Observation
14.1 General Framework
14.2 Identification of Neural Networks: From One Neuron to Deep Neural Networks
14.2.1 From One Neuron to Deep Networks
14.2.2 Data Interpolation and Identification of Neural Networks
14.2.3 Shallow Feed-Forward Neural Networks
14.2.3.1 The Approximation to W: Active Sampling
14.2.3.2 Whitening
14.2.3.3 The Recovery Strategy of the Weights wi
14.2.4 Deeper Networks
14.3 Quantized Compressed Sensing with Message Passing Reconstruction
14.3.1 Bayesian Compressed Sensing via Approximate Message Passing
14.3.2 Two-Terminal Bayesian QCS
14.4 Signal Processing in Earth Observation
14.4.1 Multi-Sensor and Multi-Resolution Data Fusion
14.4.2 Hyperspectral Unmixing Accounting for Spectral Variability
References
15 Sparse Recovery of Sound Fields Using Measurements from Moving Microphones
15.1 Problem Formulation and Signal Model
15.1.1 General Problem
15.1.2 Sparse Signal Structures
15.2 Multidimensional Sampling and Reconstruction
15.2.1 Temporal Sampling Model
15.2.2 Spatial Sampling Model
15.2.3 Spatio-Temporal Measurement Model
15.2.3.1 Finite-Length Observations in Space
15.2.3.2 Linear Equations for Parameter Recovery in Terms of Uniform Grids
15.3 Sparse Sound-Field Recovery in Frequency Domain
15.3.1 Basic Ideas for the Simplified Stationary Case
15.3.2 From Static to Dynamic Sensing
15.3.3 Sparse Recovery Along the Spectral Hypercone
15.3.4 Perfect Excitation Sequences
15.3.5 Algorithm for Sparse Recovery from Dynamic Measurements
15.3.5.1 General Case
15.3.5.2 Perfect-Excitation Case
15.4 Coherence Analysis
15.4.1 Influence of the Trajectory on the Sensing Matrix
15.4.2 Coherence of Measurements
15.4.3 Spectrally Flat Spatio-Temporal Excitation
15.5 Trajectory Optimization
15.5.1 Techniques for Measurement Matrix Optimization
15.5.2 Fast Update Scheme for Trajectory Adjustments
15.6 Summary
References
16 Compressed Sensing in the Spherical Near-Field to Far-Field Transformation
16.1 Spherical Near-Field Antenna Measurements
16.1.1 Notation
16.2 Compressed Sensing
16.3 Definition and Backgrounds
16.3.1 Wigner D-Functions and Spherical Harmonics
16.3.2 Sparse Expansions of Band-Limited Functions
16.3.3 Construction of the Sensing Matrix
16.3.3.1 RIP Condition for Sensing Matrices
16.3.3.2 Construction of Low-Coherence Sensing Matrices
16.3.4 Numerical Evaluation
16.3.4.1 Coherence Evaluation
16.3.4.2 Phase Transition Diagram: Random vs. Deterministic
16.3.5 Implementation in Spherical Near-Field Antenna Measurements
16.3.5.1 Modifying the Scheme for Time Efficiency
16.3.5.2 Extension to Arbitrary Surfaces
16.3.5.3 Implementation Considerations: Basis Mismatch
16.4 Phaseless Spherical Near-Field Antenna Measurements
16.4.1 Phaseless Measurements
16.4.1.1 Ambiguities in Phaseless Spherical Harmonics Expansion
16.4.2 Numerical Evaluation
16.4.2.1 Phase Transition Diagram
16.4.2.2 Implementation in Spherical Near-Field Antenna Measurements
16.5 Summary
References
Applied and Numerical Harmonic Analysis
Applied and Numerical Harmonic Analysis
(104 volumes)