书名:Cognitive networked sensing and big data
责任者:Robert Qiu | Michael Wicks.
摘要
Wireless Distributed Computing and Cognitive Sensing defines high-dimensional data processing in the context of wireless distributed computing and cognitive sensing. This book presents the challenges that are unique to this area such as synchronization caused by the high mobility of the nodes. The author will discuss the integration of software defined radio implementation and testbed development. The book will also bridge new research results and contextual reviews. Also the author provides an examination of large cognitive radio network; hardware testbed; distributed sensing; and distributed computing.
查看更多
前言
The idea of writing this book entitled “Cognitive Networked Sensing and Big Data” started with the plan to write a briefing book on wireless distributed computing and cognitive sensing. During our research on large-scale cognitive radio network (and its experimental testbed), we realized that big data played a central role. As a result, the book project reflects this paradigm shift. In the context, sensing roughly is equivalent to “measurement.”
We attempt to answer the following basic questions. How do we sense the radio environment using a large-scale network? What is unique to cognitive radio? What do we do with the big data? How does the sample size affect the sensing accuracy?
To address these questions, we are naturally led to ask ourselves: What mathematical tools are required? What are the state-of-the-art for the analytical tools? How these tools are used?
Our prerequisite is the graduate-level course on random variables and processes. Some familiarity with wireless communication and signal processing is useful. This book is complementary with our previous book entitled “Cognitive Radio Communications and Networking: Principles and Practice” (John Wiley and Sons 2012). This book is also complementary with another book of the first author “Introduction to Smart Grid” (John Wiley and Sons 2014). This current book can be viewed as the mathematical tools for the two Wiley books.
Chapter 1 provides the necessary background to support the rest of the book. No attempt has been made to make this book really self-contained. The book will survey many latest results in the literature. We often include preliminary tools from publications. These preliminary tools may be still too difficult for many of the audience. Roughly, our prerequisite is the graduate-level course on random variables and processes.
Chapters 2–5 (Part I) are the core of this book. The contents of these chapters should be new to most graduate students in electrical and computer engineering.
Chapter 2 deals with the sum of matrix-valued random variables. One basic question is “how does the sample size affect the accuracy.” The basic building block of the data is the sample covariance matrix, which is a random matrix. Bernstein-type concentration inequalities are of special interest.
Chapter 3 collects together the deepest mathematical theorems in this book. This chapter is really the departure point of this whole book. Chapter 2 is put before this chapter since we want the audience to understand how to deal with the basic linear functions of matrices. The theory of concentration inequality tries to answer the following question: Given a random vector x taking value in some measurable space X (which is usually some high dimensional Euclidean space), and a measurable map f : X → R, what is a good explicit bound on P (|f (x) − Ef (x)| ≥ t)? Exact evaluation or accurate approximation is, of course, the central purpose of probability theory itself. In situations where exact evaluation or accurate approximation is not possible, which is the case for many practical problems, concentration inequalities aim to do the next best job by providing rapidly decaying tail bounds. It is our goal of this book is to systemically deal with the “next best job,” when the classical probability theory fails to be valid in these situations.
The sum of random matrices is a sum of linear matrix functions. Non-linear matrix functions are encountered in practice. This motivates us to study, in Chap. 4, the concentration of measure phenomenon, unique to high dimensions. The so-called Lipschitz functions of matrices such as eigenvalues are the mathematical objects.
Chapter 5 culminates for the theoretical development of the random matrix theory. The goal of this chapter is to survey the latest results in the mathematical literature. We tried to be exhaustive in recent results. To our best knowledge, these results are never used in the engineering applications. Although the prerequisites for this chapter are highly demanding, it is out belief that the pay-off will be significant to engineering graduates if they can manage to understand the chapter.
Chapter 6 is included for completion, with the major goal for the readers to compare the parallel results with Chap. 5. Our book “Cognitive Radio Communications and Networking: Principles and Practice” (John Wiley and Sons 2012) contains complementary materials of 230 pages on this subject.
In Part II, we attempt to apply these mathematical tools to different applications. The emphasis is on the connection between the theory and the diverse applications. No attempt is made to collect all the scattered results in one place.
Chapter 7 deals with compressed sensing and recovery of sparse vectors. Concentration inequalities play the central role in the sparse recovery. The so-called restricted isometry property for sensing matrices is another aspect of stating concentration of measure.
A matrix is decomposed into the eigenvalues and the corresponding eigenvectors. When the matrix is of low rank, we can equivalently say the vector of eigenvalues are sparse. Chapter 8 deals with this aspect in the context of concentration of measure.
Statistics starts with covariance matrix estimation. In Chap. 9, we deals with this problem in high dimensions. We think that compressed sensing and low-rank matrix recovery are more basic than covariance matrix estimation.
Once the covariance matrix is estimated, we can apply the statistical information to different applications. In Chap. 10, we apply the covariance matrix to hypothesis detection in high dimensions. During the study of information plus noise model, the low-rank structure is explicitly exploited. This is one justification for putting low-rank matrix recovery (Chap. 9) before this chapter. A modern trend is to exploit the structure of the data (sparsity and low rank) during the detection theory. The research in this direction is growing rapidly. Indeed, we surveyed some latest results in this chapter.
An unexpected chapter is Chap. 11 on probability constrained optimization. Due to the recent progress (as late as 2003 by Nemirovski), optimization with probabilistic constraints, often regarded as computationally intractable in the past, may be formulated in terms of deterministic convex problems that can be solved using modern convex optimization solvers. The “closed-form” Bernstein concentration inequalities play a central role in this formulation.
In Chap. 12, we show how concentration inequalities play a central role in data friendly data processing such as low rank matrix approximation. We only want to point out the connection.
Chapter 13 is designed to put all pieces together. This chapter may be put as Chap. 1. We can see that so many problems are open. We only touched the tip of the iceberg of the big data. Chapter 1 also gives us motivations of other chapters of this book.
The first author wants to thank his students for the course in the Fall semester of 2012: ECE 7970 Random Matrices, Concentration and Networking. Their comments greatly improved this book. We also want to thank PhD students at TTU for their help in proof-reading: Jason Bonior, Shujie Hou, Xia Li, Feng Lin, and Changchun Zhang. The simulations made by Feng Lin, indeed, shaped the conceptions and formulations of many places of this book, in particular on hypothesis detection. Dr. Zhen Hu and Dr. Nan Guo at TTU are also of help for their discussions. The first author's research collaborator Professor Husheng Li (University of Tennessee at Knoxville) is acknowledged for many inspired discussions.
The first author's work has been supported, for many years, by Office of Naval Research (ONR) through the program manager Dr. Santanu K. Das (code 31). Our friend Paul James Browning is instrumental in making this book possible. This work is partly funded by National Science Foundation (NSF) through two grants (ECCS-0901420 and CNS-1247778), Office of Naval Research through two grants (N00010-10-10810 and N00014-11-1-0006), and Air Force Office of Scientific Research, via a local contractor (prime contract number FA8650-10-D-1750-Task 4). Some parts of this book were finished while the first author was a visiting professor during the summer of 2012 at the Centre for Quantifiable Quality of Service in Communication Systems (Q2S), the Norwegian University of Science and Technology (NTNU), Trondheim, Norway. Many discussions with his host Professor Yuming Jiang are acknowledged here.
The authors want to thank our editor Brett Kurzman at Springer (US) for his interest in this book. We acknowledge Rebecca Hytowitz at Springer (US) for her help.
The first author wants to thank his mentors who, for the first time, exposed him to many subjects of this book: Weigan Lin (UESTC, China) on remote sensing, Zhengde Wu (UESTC, China) on electromagnetics, Shuzhang Liu (UESTC, China) on electromagnetic materials, I-Tai Lu (Polytechnic Institute of NYU) on radio propagation, Lawrence Carin (Duke) on physics-based signal processing, Leopold Felsen on scattering, and Henry Bertoni on radio propagation in wireless channels. His industrial colleagues at GTE Labs (now Verizon Wireless) and Bell Labs (Alcatel-Lucent) greatly shaped his view.
Last, but not the least, the first author wants to thank his wife Lily Liman Li for her love, encouragement, and support that sustains him during the lonely (but exciting) book writing journey—she is always there; and his children Michelle, David and Jackie light his life. This is, indeed, a special moment to record a personal note: This summer his eldest daughter Michelle is going to drive on her own, David is happy in his high school, and Jackie smiles again. Also this summer will mark the time of one decade after his moving back to academia—after spending 8 years in industry. Wring books like this was among his deepest wishes that drove him to read mathematical papers and books while watching his TV for the last two decades. Finally, he is in memory of her mother Suxian Li who passed away in 2006. His father Dafu Qiu lives in China. His parents-in-laws Lumei Li and Jinxue Chen live with him for many years. Their love and daily encouragement really make a difference in his life.
查看更多
目录
Part I Theory
1 Mathematical Foundation 3
1.1 Basic Probability 3
1.1.1 Union Bound 3
1.1.2 Independence 4
1.1.3 Pairs of Random Variables 4
1.1.4 The Markov and Chebyshev Inequalities and Chernoff Bound 5
1.1.5 Characteristic Function and Fourier Transform 6
1.1.6 Laplace Transform of the pdf 8
1.1.7 Probability Generating Function 8
1.2 Sums of Independent (Scalar-Valued) Random Variables and Central Limit Theorem 9
1.3 Sums of Independent (Scalar-Valued) Random Variables and Classical Deviation Inequalities: Hoeffding, Bernstein, and Efron-Stein. 11
1.3.1 Transform of Probability Bounds to Expectation Bounds 12
1.3.2 Hoeffding's Inequality 12
1.3.3 Bernstein's Inequality 14
1.3.4 Efron-Stein Inequality 17
1.4 Probability and Matrix Analysis 17
1.4.1 Eigenvalues, Trace and Sums of Hermitian Matrices 17
1.4.2 Positive Semidefinite Matrices 18
1.4.3 Partial Ordering of Positive Semidefinite Matrices 19
1.4.4 Definitions of f(A) for Arbitrary f 20
1.4.5 Norms of Matrices and Vectors 21
1.4.6 Expectation 23
1.4.7 Moments and Tails 26
1.4.8 Random Vector and Jensen's Inequality 29
1.4.9 Convergence 30
1.4.10 Sums of Independent Scalar-Valued Random Variables: Chernoff's Inequality 30
1.4.11 Extensions of Expectation to Matrix-Valued Random Variables 32
1.4.12 Eigenvalues and Spectral Norm 32
1.4.13 Spectral Mapping 33
1.4.14 Operator Convexity and Monotonicity 35
1.4.15 Convexity and Monotonicity for Trace Functions 36
1.4.16 The Matrix Exponential 38
1.4.17 Golden-Thompson Inequality 38
1.4.18 The Matrix Logarithm 39
1.4.19 Quantum Relative Entropy and Bregman Divergence 40
1.4.20 Lieb's Theorem 42
1.4.21 Dilations 43
1.4.22 The Positive Semi-definite Matrices and Partial Order 44
1.4.23 Expectation and the Semidefinite Order 45
1.4.24 Probability with Matrices 45
1.4.25 Isometries 46
1.4.26 Courant-Fischer Characterization of Eigenvalues 46
1.5 Decoupling from Dependance to Independence 47
1.6 Fundamentals of Random Matrices 54
1.6.1 Fourier Method 54
1.6.2 The Moment Method 54
1.6.3 Expected Moments of Random Matrices with Complex Gaussian Entries 55
1.6.4 Hermitian Gaussian Random Matrices HGRM(n, σ2) 57
1.6.5 Hermitian Gaussian Random Matrices GRM(m, n, σ2) 59
1.7 Sub-Gaussian Random Variables 60
1.8 Sub-Gaussian Random Vectors 65
1.9 Sub-exponential Random Variables 66
1.10 ε-Nets Arguments 67
1.11 Rademacher Averages and Symmetrization 69
1.12 Operators Acting on Sub-Gaussian Random Vectors 72
1.13 Supremum of Stochastic Processes 75
1.14 Bernoulli Sequence 76
1.15 Converting Sums of Random Matrices into Sums of Random Vectors 76
1.16 Linear Bounded and Compact Operators 79
1.17 Spectrum for Compact Self-Adjoint Operators 80
2 Sums of Matrix-Valued Random Variables 85
2.1 Methodology for Sums of Random Matrices85
2.2 Matrix Laplace Transform Method 87
2.2.1 Method 1—Harvey's Derivation 87
2.2.2 Method 2—Vershynin's Derivation 91
2.2.3 Method 3—Oliveria's Derivation 94
2.2.4 Method 4—Ahlswede-Winter's Derivation 95
2.2.5 Derivation Method 5—Gross, Liu, Flammia, Becker, and Eisert 106
2.2.6 Method 6—Recht's Derivation 106
2.2.7 Method 7—Derivation by Wigderson and Xiao 107
2.2.8 Method 8—Tropp's Derivation 107
2.3 Cumulate-Based Matrix-Valued Laplace Transform Method 108
2.4 The Failure of the Matrix Generating Function 109
2.5 Subadditivity of the Matrix Cumulant Generating Function 110
2.6 Tail Bounds for Independent Sums 111
2.6.1 Comparison Between Tropp's Method and Ahlswede–Winter Method 114
2.7 Matrix Gaussian Series—Case Study 115
2.8 Application: A Gaussian Matrix with Nonuniform Variances 118
2.9 Controlling the Expectation 119
2.10 Sums of Random Positive Semidefinite Matrices 121
2.11 Matrix Bennett and Bernstein Inequalities 125
2.12 Minimax Matrix Laplace Method 128
2.13 Tail Bounds for All Eigenvalues of a Sum of Random Matrices 128
2.14 Chernoff Bounds for Interior Eigenvalues 131
2.15 Linear Filtering Through Sums of Random Matrices 134
2.16 Dimension-Free Inequalities for Sums of Random Matrices 137
2.17 Some Khintchine-Type Inequalities 140
2.18 Sparse Sums of Positive Semi-definite Matrices 144
2.19 Further Comments 144
3 Concentration of Measure 145
3.1 Concentration of Measure Phenomenon 145
3.2 Chi-Square Distributions 146
3.3 Concentration of Random Vectors 148
3.4 Slepian-Fernique Lemma and Concentration of Gaussian Random Matrices 159
3.5 Dudley's Inequality 162
3.6 Concentration of Induced Operator Norms 165
3.7 Concentration of Gaussian and Wishart Random Matrices 173
3.8 Concentration of Operator Norms 180
3.9 Concentration of Sub-Gaussian Random Matrices 185
3.10 Concentration for Largest Eigenvalues 190
3.10.1 Talagrand's Inequality Approach 191
3.10.2 Chaining Approach 192
3.10.3 General Random Matrices 193
3.11 Concentration for Projection of Random Vectors 194
3.12 Further Comments 198
4 Concentration of Eigenvalues and Their Functionals 199
4.1 Supremum Representation of Eigenvalues and Norms 199
4.2 Lipschitz Mapping of Eigenvalues 202
4.3 Smoothness and Convexity of the Eigenvalues of a Matrix and Traces of Matrices 203
4.4 Approximation of Matrix Functions Using Matrix Taylor Series 211
4.5 Talagrand Concentration Inequality 216
4.6 Concentration of the Spectral Measure for Wigner Random Matrices 218
4.7 Concentration of Noncommutative Polynomials in Random Matrices 222
4.8 Concentration of the Spectral Measure for Wishart Random Matrices 223
4.9 Concentration for Sums of Two Random Matrices 235
4.10 Concentration for Submatrices 237
4.11 The Moment Method 238
4.12 Concentration of Trace Functionals 243
4.13 Concentration of the Eigenvalues 244
4.14 Concentration for Functions of Large Random Matrices: Linear Spectral Statistics 246
4.15 Concentration of Quadratic Forms 249
4.16 Distance Between a Random Vector and a Subspace 257
4.17 Concentration of Random Matrices in the Stieltjes Transform Domain 261
4.18 Concentration of von Neumann Entropy Functions 264
4.19 Supremum of a Random Process 267
4.20 Further Comments 268
5 Non-asymptotic, Local Theory of Random Matrices 271
5.1 Notation and Basics 272
5.2 Isotropic Convex Bodies 273
5.3 Log-Concave Random Vectors 275
5.4 Rudelson's Theorem 277
5.5 Sample Covariance Matrices with Independent Rows 281
5.6 Concentration for Isotropic, Log-Concave Random Vectors 290
5.6.1 Paouris' Concentration Inequality 290
5.6.2 Non-increasing Rearrangement and Order Statistics 292
5.6.3 Sample Covariance Matrix 293
5.7 Concentration Inequality for Small Ball Probability 295
5.8 Moment Estimates 299
5.8.1 Moments for Isotropic Log-Concave Random Vectors 299
5.8.2 Moments for Convex Measures 303
5.9 Law of Large Numbers for Matrix-Valued Random Variables 305
5.10 Low Rank Approximation 309
5.11 Random Matrices with Independent Entries 313
5.12 Random Matrices with Independent Rows 314
5.12.1 Independent Rows 314
5.12.2 Heavy-Tailed Rows 316
5.13 Covariance Matrix Estimation 320
5.13.1 Estimating the Covariance of Random Matrices 322
5.14 Concentration of Singular Values 324
5.14.1 Sharp Small Deviation 325
5.14.2 Sample Covariance Matrices 325
5.14.3 Tall Matrices 326
5.14.4 Almost Square Matrices 326
5.14.5 Square Matrices 327
5.14.6 Rectangular Matrices 327
5.14.7 Products of Random and Deterministic Matrices 329
5.14.8 Random Determinant 331
5.15 Invertibility of Random Matrix 334
5.16 Universality of Singular Values 337
5.16.1 Random Matrix Plus Deterministic Matrix 341
5.16.2 Universality for Covariance and Correlation Matrices 345
5.17 Further Comments 349
6 Asymptotic, Global Theory of Random Matrices 351
6.1 Large Random Matrices 351
6.2 The Limit Distribution Laws 352
6.3 The Moment Method 353
6.4 Stieltjes Transform 354
6.5 Free Probability 358
6.5.1 Concept 358
6.5.2 Practical Significance 359
6.5.3 Definitions and Basic Properties 360
6.5.4 Free Independence 362
6.5.5 Free Convolution 364
6.6 Tables for Stieltjes, R- and S-Transforms 365
Part II Applications
7 Compressed Sensing and Sparse Recovery 371
7.1 Compressed Sensing 371
7.2 Johnson–Lindenstrauss Lemma and Restricted Isometry Property 374
7.3 Structured Random Matrices 383
7.3.1 Partial Random Fourier Matrices 384
7.4 Johnson–Lindenstrauss Lemma for Circulant Matrices 384
7.5 Composition of a Random Matrix and a Deterministic Dictionary 384
7.6 Restricted Isometry Property for Partial Random Circulant Matrices 392
7.7 Restricted Isometry Property for Time-Frequency Structured Random Matrices 400
7.8 Suprema of Chaos Processes 405
7.9 Concentration for Random Toeplitz Matrix 408
7.10 Deterministic Sensing Matrices 410
8 Matrix Completion and Low-Rank Matrix Recovery 411
8.1 Low Rank Matrix Recovery 411
8.2 Matrix Restricted Isometry Property 413
8.3 Recovery Error Bounds 414
8.4 Low Rank Matrix Recovery for Hypothesis Detection 415
8.5 High-Dimensional Statistics 416
8.6 Matrix Compressed Sensing 417
8.6.1 Observation Model 417
8.6.2 Nuclear Norm Regularization 418
8.6.3 Restricted Strong Convexity 418
8.6.4 Error Bounds for Low-Rank Matrix Recovery 419
8.7 Linear Regression 423
8.8 Multi-task Matrix Regression 427
8.9 Matrix Completion 429
8.9.1 Orthogonal Decomposition and Orthogonal Projection 430
8.9.2 Matrix Completion 432
8.10 Von Neumann Entropy Penalization and Low-Rank Matrix Estimation 434
8.10.1 System Model and Formalism 435
8.10.2 Sampling from an Orthogonal Basis 436
8.10.3 Low-Rank Matrix Estimation 437
8.10.4 Tools for Low-Rank Matrix Estimation 439
8.11 Sum of a Large Number of Convex Component Functions 440
8.12 Phase Retrieval via Matrix Completion 443
8.12.1 Methodology 444
8.12.2 Matrix Recovery via Convex Programming 446
8.12.3 Phase Space Tomography 447
8.12.4 Self-Coherent RF Tomography 449
8.13 Further Comments 456
9 Covariance Matrix Estimation in High Dimensions 457
9.1 Big Picture: Sense, Communicate, Compute, and Control 457
9.1.1 Received Signal Strength (RSS) and Applications to Anomaly Detection 460
9.1.2 NC-OFDM Waveforms and Applications to Anomaly Detection 460
9.2 Covariance Matrix Estimation 461
9.2.1 Classical Covariance Estimation 461
9.2.2 Masked Sample Covariance Matrix 463
9.2.3 Covariance Matrix Estimation for Stationary Time Series 474
9.3 Covariance Matrix Estimation 475
9.4 Partial Estimation of Covariance Matrix 476
9.5 Covariance Matrix Estimation in Infinite-Dimensional Data 478
9.6 Matrix Model of Signal Plus Noise Y = S + X 479
9.7 Robust Covariance Estimation 485
10 Detection in High Dimensions 487
10.1 OFDM Radar 487
10.2 Principal Component Analysis 488
10.2.1 PCA Inconsistency in High-Dimensional Setting 490
10.3 Space-Time Coding Combined with CS 490
10.4 Sparse Principal Components 490
10.5 Information Plus Noise Model Using Sums of Random Vectors. 491
10.6 Information Plus Noise Model Using Sums of Random Matrices 492
10.7 Matrix Hypothesis Testing 494
10.8 Random Matrix Detection 495
10.9 Sphericity Test with Sparse Alternative 501
10.10 Connection with Random Matrix Theory 502
10.10.1 Spectral Methods 502
10.10.2 Low Rank Perturbation of Wishart Matrices 503
10.10.3 Sparse Eigenvalues 503
10.11 Sparse Principal Component Detection 503
10.11.1 Concentration Inequalities for the k-Sparse Largest Eigenvalue 504
10.11.2 Hypothesis Testing with λk max 505
10.12 Semidefinite Methods for Sparse Principal Component Testing 506
10.12.1 Semidefinite Relaxation for λk max 506
10.12.2 High Probability Bounds for Convex Relaxation 508
10.12.3 Hypothesis Testing with Convex Methods 508
10.13 Sparse Vector Estimation 509
10.14 Detection of High-Dimensional Vectors 511
10.15 High-Dimensional Matched Subspace Detection 514
10.16 Subspace Detection of High-Dimensional Vectors Using Compressive Sensing 516
10.17 Detection for Data Matrices 520
10.18 Two-Sample Test in High Dimensions 520
10.19 Connection with Hypothesis Detection of Noncommuntative Random Matrices 525
10.20 Further Notes 526
11 Probability Constrained Optimization 527
11.1 The Problem 527
11.2 Sums of Random Symmetric Matrices 529
11.3 Applications of Sums of Random Matrices 536
11.4 Chance-Constrained Linear Matrix Inequalities 542
11.5 Probabilistically Constrained Optimization Problem 543
11.6 Probabilistically Secured Joint Amplify-and-Forward Relay by Cooperative Jamming 547
11.6.1 Introduction 547
11.6.2 System Model 548
11.6.3 Proposed Approach 552
11.6.4 Simulation Results 556
11.7 Further Comments 556
12 Database Friendly Data Processing 559
12.1 Low Rank Matrix Approximation 559
12.2 Row Sampling for Matrix Algorithms 560
12.3 Approximate Matrix Multiplication 562
12.4 Matrix and Tensor Sparsification 564
12.5 Further Comments 566
13 From Network to Big Data 567
13.1 Large Random Matrices for Big Data 567
13.2 A Case Study for Hypothesis Detection in High Dimensions 569
13.3 Cognitive Radio Network Testbed 571
13.4 Wireless Distributed Computing 571
13.5 Data Collection 572
13.6 Data Storage and Management 572
13.7 Data Mining of Large Data Sets 573
13.8 Mobility of Network Enabled by UAVs 573
13.9 Smart Grid 574
13.10 From Cognitive Radio Network to Complex Network and to Random Graph 574
13.11 Random Matrix Theory and Concentration of Measure 574
Bibliography 577
Index 603
查看更多
作者简介
Dr. Qiu is a Professor in the Department of Electrical and Computer Engineering, Center for Manufacturing PA\Research, Tennessee Technological University, Cookeville, Tennessee
查看更多
馆藏单位
中科院文献情报中心