凸优化在信号处理与通信中的应用Convex Optimization in Signal Processing and Communications

【实例简介】
凸优化理论在信号处理以及通信系统中的应用 比较经典的通信系统凸优化入门教程
Contents List of contributors page Ix Preface Automatic code generation for real- time convex optimization Jacob Mattingley and stephen Boyd 1.1 Introduction 1.2 Solvers and specification languages 6 1. 3 Examples 12 1. 4 Algorithm considerations 1.5 Code generation 26 1.6 CVXMOD: a preliminary implementation 28 1.7 Numerical examples 29 1. 8 Summary, conclusions, and implications Acknowledgments 35 References Gradient-based algorithms with applications to signal-recovery problems Amir beck and marc teboulle 2.1 Introduction 42 2.2 The general optimization model 43 2.3 Building gradient-based schemes 46 2. 4 Convergence results for the proximal-gradient method 2.5 A fast proximal-gradient method 2.6 Algorithms for l1-based regularization problems 67 2.7 TV-based restoration problems 2. 8 The source-localization problem 77 2.9 Bibliographic notes 83 References 85 Contents Graphical models of autoregressive processes 89 Jitkomut Songsiri, Joachim Dahl, and Lieven Vandenberghe 3.1 Introduction 89 3.2 Autoregressive processes 92 3.3 Autoregressive graphical models 98 3. 4 Numerical examples 104 3.5 Conclusion 113 Acknowledgments 114 References 114 SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications Zhi-Quan Luo and Tsung-Hui Chang 4.1 Introduction 117 4.2 Nonconvex QCQPs and sDP relaxation 118 4.3 SDP relaxation for separable homogeneous QCQPs 123 4.4 SDP relaxation for maximization homogeneous QCQPs 137 4.5 SDP relaxation for fractional QCQPs 143 4.6 More applications of SDP relaxation 156 4.7 Summary and discussion 161 Acknowledgments 162 References 162 Probabilistic analysis of semidefinite relaxation detectors for multiple-input, multiple-output systems 166 Anthony Man-Cho So and Yinyu Ye 5.1 Introduction 166 5.2 Problem formulation 169 5.3 Analysis of the SDr detector for the MPsK constellations 172 5.4 Extension to the Qam constellations 179 5.5 Concluding remarks 182 Acknowledgments 182 References 189 Semidefinite programming matrix decomposition, and radar code design 192 Yongwei Huang, Antonio De Maio, and Shuzhong Zhang 6.1 Introduction and notation 192 6.2 Matrix rank-1 decomposition 194 6.3 Semidefinite programming 200 6.4 Quadratically constrained quadratic programming and ts sdp relaxation 201 Contents 6.5 Polynomially solvable QCQP problems 203 6.6 The radar code-design problem 208 6.7 Performance measures for code design 211 6.8 Optimal code design 214 6.9 Performance analysis 218 6.10 Conclusions 223 References 226 Convex analysis for non-negative blind source separation with application in imaging 22 Wing-Kin Ma, Tsung-Han Chan, Chong-Yung Chi, and Yue Wang 7.1 Introduction 229 7.2 Problem statement 231 7.3 Review of some concepts in convex analysis 236 7.4 Non-negative, blind source-Separation criterion via CAMNS 238 7.5 Systematic linear-programming method for CAMNS 245 7.6 Alternating volume-maximization heuristics for CAMNS 248 7.7 Numerical results 252 7.8 Summary and discussion 257 Acknowledgments 263 References 263 Optimization techniques in modern sampling theory 266 Tomer Michaeli and yonina c. eldar 8.1 Introduction 266 8.2 Notation and mathematical preliminaries 268 8.3 Sampling and reconstruction setup 270 8.4 Optimization methods 278 8.5 Subspace priors 280 8.6 Smoothness priors 290 8.7 Comparison of the various scenarios 300 8.8 Sampling with noise 302 8. 9 Conclusions 310 Acknowledgments 311 References 311 Robust broadband adaptive beamforming using convex optimization Michael Rubsamen, Amr El-Keyi, Alex B Gershman, and Thia Kirubarajan 9.1 Introduction 315 9.2 Background 317 9.3 Robust broadband beamformers 321 9.4 Simulations 330 Contents 9.5 Conclusions 337 Acknowledgments 337 References 337 Cooperative distributed multi-agent optimization 340 Angelia Nedic and asuman ozdaglar 10.1 Introduction and motivation 340 10.2 Distributed-optimization methods using dual decomposition 343 10.3 Distributed-optimization methods using consensus algorithms 358 10.4 Extensions 372 10.5 Future work 378 10.6 Conclusions 380 10.7 Problems 381 References 384 Competitive optimization of cognitive radio MIMO systems via game theory 387 Gesualso Scutari, Daniel P Palomar, and Sergio Barbarossa 11.1 Introduction and motivation 387 11.2 Strategic non-cooperative games: basic solution concepts and algorithms 393 11.3 Opportunistic communications over unlicensed bands 4 11.4 Opportunistic communications under individual-interference constraints 415 1.5 Opportunistic communications under global-interference constraints 431 11.6 Conclusions 438 Ack gment 439 References 439 12 Nash equilibria: the variational approach 443 Francisco Facchinei and Jong-Shi Pang 12.1 Introduction 443 12.2 The Nash-equilibrium problem 44 12. 3 EXI 455 12.4 Uniqueness theory 466 12.5 Sensitivity analysis 472 12.6 Iterative algorithms 478 12.7 A communication game 483 Acknowledgments 490 References 491 Afterword 494 Index 49 Contributors Sergio Barbarossa Yonina c, eldar University of rome-La Sapienza Technion-Israel Institute of Technology Haifa Israel Amir beck Technion-Israel institute Amr El-Keyi of Technology Alexandra university Haif Egypt Israel Francisco facchini Stephen boyd University of rome La sapienza Stanford University Rome California Italy USA Alex b, gershman Tsung-Han Chan Darmstadt University of Technology National Tsing Hua University Darmstadt Hsinchu Germany T aiwan Yongwei Huang Tsung-Hui Chang Hong Kong university of science National Tsing Hua University and Technology Hsinchu Hong Kong Taiwan Thia Kirubarajan Chong-Yung chi McMaster University National Tsing Hua University Hamilton ontario Hsinchu Canada Taiwan Zhi-Quan Luo Joachim dahl University of minnesota anybody Technology A/s Minneapolis Denmark USA List of contributors Wing-Kin Ma Michael rebsamen Chinese University of Hong Kong Darmstadt University Hong Kon Technology Darmstadt Antonio de maio Germany Universita degli studi di napoli Federico ii Gesualdo scutari Naples Hong Kong University of Science aly and Technology Hong Kong Jacob Mattingley Anthony Man-Cho So Stanford University Chinese University of Hong Kong California Hong Kong USA Jitkomut songsin Tomer michaeli University of california Technion-Israel institute LoS Angeles. California ogy USA Haifa Marc teboulle Tel-Aviv University Angelia Nedic Tel-Av University of Illinois at Israel Urbana-Champaign InoS Lieven Vandenberghe USA University of California Los Angeles, California USA Asuman Ozdaglar Massachusetts Institute of Technology Yue Wang Boston massachusetts Virginia Polytechnic Institute USA and State University Arlington Daniel p palomar USA Hong Kong University of Science and Technology Yinyu Ye Hong Kong Stanford University California ong-Shi Pang USA University of illinois at Urbana-Champaign Shuzhong zhang Illinois Chinese university of Hong Kong USA Hong Kong Preface The past two decades have witnessed the onset of a surge of research in optimization. This includes theoretical aspects, as well as algorithmic developments such as gener alizations of interior-point methods to a rich class of convex-optimization problems The development of general-purpose software tools together with insight generated by the underlying theory have substantially enlarged the set of engineering-design problems that can be reliably solved in an efficient manner. The engineering community has greatly benefited from these recent advances to the point where convex optimization has now emerged as a major signal-processing technique on the other hand, innovative applica- tions of convex optimization in signal processing combined with the need for robust and efficient methods that can operate in real time have motivated the optimization commu- nity to develop additional needed results and methods. The combined efforts in both the optimization and signal-processing communities have led to technical breakthroughs in a wide variety of topics due to the use of convex optimization This includes solutions to numerous problems previously considered intractable; recognizing and solving convex- optimization problems that arise in applications of interest; utilizing the theory of convex optimization to characterize and gain insight into the optimal-solution structure and to derive performance bounds; formulating convex relaxations of difficult problems; and developing general purpose or application-driven specific algorithms, including those that enable large-scale optimization by exploiting the problem structure This book aims at providing the reader with a series of tutorials on a wide variety of convex-optimization applications in signal processing and communications, written by worldwide leading experts, and contributing to the diffusion of these new devel opments within the signal-processing community. The goal is to introduce convex optimization to a broad signal-processing community, provide insights into how convex optimization can be used in a variety of different contexts, and showcase some notable successes. The topics included are automatic code generation for real-time solvers, graph ical models for autoregressive processes, gradient-based algorithms for signal-recovery applications, semidefinite programming(SDP)relaxation with worst-case approximation performance, radar waveform design via SDP, blind non-negative source separation for image processing, modern sampling theory, robust broadband beamforming techniques distributed multiagent optimization for networked systems, cognitive radio systems via game theory, and the variational-inequality approach for Nash-equilibrium solutions Preface There are excellent textbooks that introduce nonlinear and convex optimization, pro viding the reader with all the basics on convex analysis, reformulation of optimization problems, algorithms, and a number of insightful engineering applications. This book is targeted at advanced graduate students, or advanced researchers that are already familiar with the basics of convex optimization. It can be used as a textbook for an advanced grad uate course emphasizing applications, or as a complement to an introductory textbook that provides up-to-date applications in engineering. It can also be used for self-study to become acquainted with the state of-the-art in a wide variety of engineering topics This book contains 12 diverse chapters written by recognized leading experts world wide, covering a large variety of topics. Due to the diverse nature of the book chapters it is not possible to organize the book into thematic areas and each chapter should be treated independently of the others. a brief account of each chapter is given next In Chapter 1, Mattingley and Boyd elaborate on the concept of convex optimization in real-time embedded systems and automatic code generation. As opposed to generic solvers that work for general classes of problems, in real-time embedded optimization the same optimization problem is solved many times, with different data, often with a hard real-time deadline. Within this setup the authors propose an automatic code-generation system that can then be compiled to yield an extremely efficient custom solver for the problem family In Chapter 2, Beck and Teboulle provide a unified view of gradient-based algorithms for possibly nonconvex and non-differentiable problems, with applications to signal recovery. They start by rederiving the gradient method from several different perspec tives and suggest a modification that overcomes the slow convergence of the algorithm They then apply the developed framework to different image-processing problems such as e1-based regularization, TV-based denoising, and Tv-based deblurring, as well as communication applications like source localization In Chapter 3, Songsiri, Dahl, and Vandenberghe consider graphical models for autore- gressive processes. They take a parametric approach for maximum-likelihood and maximum-entropy estimation of autoregressive models with conditional independence constraints, which translates into a sparsity pattern on the inverse of the spectral-density matrix. These constraints turn out to be nonconvex. To treat them the authors propose a relaxation which in some cases is an exact reformulation of the original problem. The proposed methodology allows the selection of graphical models by fitting autoregressive processes to different topologies and is illustrated in different applications The following three chapters deal with optimization problems closely related to SDP and relaxation techniques In Chapter 4, Luo and Chang consider the SDP relaxation for several classes of quadratic-optimization problems such as separable quadratically constrained quadratic programs(QCQPs)and fractional QCQPs, with applications in communications and sig nal processing. They identify cases for which the relaxation is tight as well as classes of quadratic-optimization problems whose relaxation provides a guaranteed, finite worst case approximation performance. Numerical simulations are carried out to assess the efficacy of the SDP-relaxation approach 【实例截图】
【核心代码】