EE 609: Convex Optimization in SP/COM

  1. Instructors: Ketan Rajawat
  2. Prerequisites: Linear Algebra, Probability
  3. Objective: Convex optimization has recently been applied to a wide variety of problems in EE, especially in signal processing, communications, and networks. The aim of this course is to train the students in application and analysis of convex optimization problems in signal processing and wireless communications. At the end of this course, the students are expected to:
    1. Know about the applications of convex optimization in signal processing, wireless communications, and networking research.
    2. Be able to recognize convex optimization problems arising in these areas.
    3. Be able to recognize ‘hidden’ convexity in many seemingly non-convex problems; formulate them as convex problems. 
    4. Be able to develop low-complexity, approximate solutions for difficult non-convex problems.
  4. References:
    1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press. [Online]. http://www.stanford.edu/~boyd/cvxbook/
    2. Convex Optimization in Signal Processing and Communications, D. P. Palomar, Y. C. Eldar. Cambridge Press, 2010.
    3. IEEE Signal Processing Magazine- Special Issue on Advances in Convex Optimization, Vol. 27, No. 3, May 2010.
    4. Dimitri P. Bertsekas, Convex Analysis and Optimization, Athena-Scientific, 2003.
  5. Format (tentative)
    1. Major quiz (10) scheduled on 6 Feb. (Monday)
    2. Mid-sem exam (20) schedule TBA
    3. End-sem exam (35) schedule TBA
    4. 7 Assignments (10) 
    5. 1 Term paper (25)
  6. Time and place: Monday 11am, Thursday, Friday 10am, L17
  7. This course will cover (approximately) 
    1. Background on linear algebra
    2. Convex sets, functions, and problems
    3. Examples of convex problems: LP, QCQP, SOCP
    4. Duality, KKT conditions
    5. Geometric programming and applications
    6. Linear and quadratic classification
    7. Network optimization
    8. Sparse regression, Lasso, ridge regression and applications in image processing
    9. Robust least squares and applications in signal processing
    10. Support vector machines and applications in machine learning
    11. Semidefinite programming and applications in experiment design
    12. Semidefinite relaxation and applications in MIMO detection, integer programming
    13. Low rank matrix completion and applications in recommendor systems
    14. Multidimensional scaling and applications in sensor localization
    15. Numerical linear algebra, basics of interior point methods
  8. Tentative list of topics for Term Paper 
    1. Convex optimization in game theory
    2. Total least squares
    3. Nonlinear classification via kernel methods
    4. Integer programming techniques
    5. Majorization-minimization technique for solving non-convex problems
    6. FIR filter design
    7. Multiobjective optimization, pareto optimality
    8. Capacity-rate distortion duality and interpretation
    9. Robust optimization
    10. Signomial programming in power control
    11. Difference of convex programming 
    12. Face detection/recognition via SVMs
    13. Numerical algorithms for L1 norm minimization
    14. Semidefinite relaxation for quadratic optimization problems
    15. Principal compoenent analysis and applications
    16. Convex optimization is speech processing/recognition
    17. Convex optimization applications in image processing
    18. Distributed convex optimization for resource allocation in networks
    19. Network flow problem, total unimodularity, network simplex
    20. Gradient descent algorithm, Newton method, and convergence resutls
    21. Real-time convex optimization in signal processing
    22. Stochastic gradient descent and convergence
    23. Learning sparse dictionaries for image compression
    24. Cross-layer optimization for resource allocation in networks
    25. Convex optimization in finance
    26. Alternating minimization and coordinate descent methods 
    27. Augmented Lagrangian method
    28. Behind cvx: self-dual minimization, interior point methods
    29. Convex optimization applications for ML estimation
    30. Genetic algorihtms for non-convex optimization
    31. SDP relaxation detectors for MIMO systems
    32. Algorithms for low-rank matrix factorization
    33. Nonnegative blind source separation
    34. Convexity and submodularity
    35. Robust adaptive beamforming
    36. Solving very large-scale convex optimization problems
    37. Subgradient method and applications
    38. Saddle point methods for convex optimization
    39. Convex optimization for visualizing high dimensional data