Difference between revisions of "EE 599 Graph Signal Processing"

From WikiBiron
m (Created page with '== EE 599, Graph Signal Processing, Fall 2013 == '''Course Description:''' The theory and application of wavelet decomposition of signals. Includes subband coding, image compress…')
 
m (→‎Schedule)
 
(43 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
== EE 599, Graph Signal Processing, Fall 2013 ==
+
== EE 599, Graph Signal Processing, Fall 2015 ==
−
'''Course Description:''' The theory and application of wavelet decomposition of signals. Includes subband coding, image compression, multiresolution signal processing, filter banks, and time-frequency tilings.
+
'''Course Description:''' Theory and applications of emerging tools for signal processing on graphs, including a review of spectral graph theory and newly developed ideas filtering, downsampling, multiresolution decompositions and wavelet transforms"
  
−
'''Prerequisites:''' ''EE 483, Introduction to Digital Signal Processing'' and ''EE 441, Applied Linear Algebra for Engineering'', or equivalent courses. Please note that the course will assume some knowledge of standard DSP concepts as well as of some basic linear algebra. If you took these two courses some time ago it would be a good idea to review some of the key material early in the semester.
+
'''Prerequisites:''' ''EE 483, Introduction to Digital Signal Processing'' and ''EE 441, Applied Linear Algebra for Engineering'', or equivalent courses. Please note that the course will assume some knowledge of standard DSP concepts as well as of some basic linear algebra. If you took these two courses some time ago it would be a good idea to review some of the key material early in the semester
 +
 
 +
'''Background:'''  Graphs have long been used in a wide variety of problems, such
 +
analysis of social networks, machine learning, network protocol
 +
optimization, decoding of LDPCs or image processing. Techniques based
 +
on spectral graph theory provide a "frequency" interpretation of graph
 +
data and have proven to be quite popular in many of these
 +
applications.
 +
In the last few years, a growing amount of work has started extending
 +
and complementing spectral graph techniques, leading to the emergence
 +
of "Graph Signal Processing" as a broad research field. A common
 +
characteristic of this recent work is that it considers the data
 +
attached to the vertices as a "graph-signal" and seeks to create new
 +
techniques (filtering, sampling, interpolation),  similar to those
 +
commonly used in conventional signal processing (for audio, images or
 +
video), so that they can be applied to these graph signals.
 +
 
 +
'''Goals:'''  In this class we provide an overview of this emerging area. The course
 +
is aimed at graduate students who have already completed basic
 +
coursework in the general areas of signal processing, communications
 +
and controls. We start with a review of core concepts, including a
 +
review of relevant linear algebra and signal processing concepts. This
 +
will be followed by a discussion of advanced topics, focusing on how
 +
well established concepts in signal processing are being extended to
 +
graph signals (most of this work has taken place in the last 10
 +
years).  Finally, we will study specific applications of graph signal
 +
processing methods.
  
 
== Instructor ==
 
== Instructor ==
Line 18: Line 44:
  
 
== Schedule ==
 
== Schedule ==
−
* '''Lectures''' Tuesday and Thursday, 11-12:20pm, KAP 147
+
* '''Lectures''' Tuesday and Thursday, 11:00am-12:20pm, WPH 106
−
* '''Office hours''' Tuesday and Thursday, 1:30-3:30pm, EEB 436, and by appointment.
+
* '''Office hours''' Tuesday and Thursday, 2-3:30pm, EEB 436, and by appointment.
−
* '''Midterm 1''' Tuesday Oct 23, 2012, in class
+
* '''Midterm''' , Thursday, Nov 5, 11am-12:20pm, in class, room WPH 106.
−
* '''Midterm 2''' Thursday Nov 15, 2012, in class  
 
 
* '''Final''' There will be no final exam
 
* '''Final''' There will be no final exam
  
 
== Grading ==
 
== Grading ==
−
Each midterm will account for 30% of the grade. The remaining 40% will be based on  a project. The final project report will be due on Dec 14, 2012. Project presentations will be on Dec 10, 2012.
+
Class participation and homework (20%), Midterm (40%), Project (40%). The final project reports will be due on TBD.
  
−
== DEN Access ==
+
== Material Covered (Subject to Change) ==
−
This semester I will use the Blackboard system offered by DEN to post assignments and solutions, as well as grades. Please register with DEN and create your DEN profile as soon as possible by following the instructions on the DEN Webpage. Please note that materials from Fall 2010, video lectures and class notes, are available on DEN. I will be using these videos and notes throughout this semester.
+
* '''Week 1''': Introduction -- Why Graph Signal Processing: concepts, applications and challenges
−
 
+
* '''Week 2''': Introduction to graph concepts -- Linear algebra review
−
== Lectures ==
+
* '''Week 3''': Spectral graph theory -- Orthogonal transforms review
−
*Lecture 1 (8/28/12)
+
* '''Week 4''':Frequency interpretation -- Nodal Theorems
−
** Introduction, goals, historical perspective
+
* '''Week 5''': Graph filtering -- Vertex and Spectral interpretations
−
*Lecture 2 (8/30/12)
+
* '''Week 6''':Advanced Topic 1: Shift invariance, localization and uncertainty principles
−
** Uncertainty principle
+
* '''Week 7''': Advanced Topic 2: Downsampling
−
** Practical time frequency localization example
+
* '''Week 8''':Advanced Topic 3: Wavelets
−
** Signal spaces
+
* '''Week 9''':Advanced Topic 4: Multiresolution and graph approximation
−
*Lecture 3 (9/4/12)
+
* '''Week 10''':Advanced Topic 5: Directed Graphs --- Midterm
−
** Piecewise constant signals and Haar Wavelets
+
* '''Week 11''':Application 1: Image Processing
−
** Bases
+
* '''Week 12''':Application 2: Sensor Networks
−
** Norms
+
* '''Week 13''':Application 3: Machine Learning
−
*Lecture 4 (9/6/12)
+
* '''Week 14''':Application 4: Finite State Machines
−
** View lectures 1-4 from 2010
+
* '''Week 15''': Project Discussions and Presentations
−
*Lecture 5 (9/11/12)
 
−
** View lecture 4-5 from 2010
 
−
** Spaces, subspaces, orthogonal complements, successive approximation
 
−
*Lecture 6 (9/13/12)
 
−
** Haar Wavelet construction, discrete time Haar construction example
 
−
*Lecture 7 (9/18/12)
 
−
** View lecture 6-7 from 2010
 
−
** Bi-orthogonal bases, overcomplete representations
 
−
*Lecture 8 (9/20/12)
 
−
**View Lecture 8-9 from 2010
 
−
* No Lecture on 9/25/12
 
−
*Lecture 9 (9/27/12)
 
−
**View Lecture 10 from 2010
 
−
**Criteria to select a representation in an overcomplete set
 
−
**Why is sparsity useful?
 
−
**Least squares solution, brute force search
 
−
*Lecture 10 (10/2/12)
 
−
**Matching pursuits and Orthogonal Matching Pursuits
 
−
**Why does l1 promote sparsity?
 
−
**Basis pursuit
 
−
*Lecture 11 (10/4/12)
 
−
**Compressed sensing
 
−
** Discussion of compressed sensing requirements and applications
 
−
*Lecture 12 (10/9/12)
 
−
** View Lectures 11-12 from 2010
 
−
** Multirate signal processing
 
−
** Modulation domain representation of filterbanks
 
−
*Lecture 13 (10/11/12)
 
−
** Time domain representation, polyphase domain representation
 
−
*Lecture 14 (10/16/12)
 
−
** Polyphase domain representation, QMF solutions
 
−
*Lecture 15 (10/18/12)
 
−
** Review session -- Problems
 
−
*Midterm #1 (10/23/12)
 
−
*Lecture 16 (10/25/12)
 
−
** View lectures 13-15, 2010
 
−
** Orthogonal filterbank solutions
 
−
*Lecture 17 (10/30/12)
 
−
** View Lecture 16-17, 2010
 
−
** Adaptive bases
 
−
** Wavelet packets
 
−
** Examples
 
−
*Lecture 18 (11/1/12)
 
−
** Bi-orthogonal conditions and solutions
 
−
*Lecture 19 (11/6/12)
 
−
** View lectures 18-20, 2010
 
−
** Lifting
 
−
*Lecture 20 (11/8/12)
 
−
** Multichannel transforms
 
−
** Multidimensional transforms
 
  
 
== Texbooks ==
 
== Texbooks ==
−
'''Required:'''
+
* No required textbook. The reference material will include textbooks as well as a number of recent articles
−
* Martin Vetterli and Jelena Kovacevic, Wavelets and Subband Coding, Prentice Hall, 1995. This textbook is now available electronically at http://www.waveletsandsubbandcoding.org
 
−
* Matlab Wavelet Toolbox, This toolbox is available on the student computer accounts.
 
  
−
'''Recommended:'''
+
== References ==
−
* Gilbert Strang and Truong Q. Nguyen, Wavelets and Filter Banks, Wellesley-Cambridge Press, 1995
 
−
* Stephane Mallat, A Wavelet Tour of Signal Processing: The Sparse Way, 3rd Ed., Academic Press - Elsevier, 2009
 
−
* P. P. Vaidyanathan, Multirate Systems and Filter Banks , Prentice Hall, 1993
 
  
−
== Material Covered (Subject to Change) ==
+
Partial list -- more to be added during the semester
−
* '''Weeks 1 and 2''' Introduction and Motivation. Signal representation using bases. Hilbert spaces. Orthogonal, bi-orthogonal basis and overcomplete expansions. Example: representing finite energy continuous signals using Haar basis. Example of construction of Haar basis
 
−
* '''Week 3''' Bases for discrete signals. Finite and infinite dimensional spaces.
 
−
* '''Week 4''' Overcomplete expansions. Searching for the best representation. Matching pursuits and variations. Compressed sensing.
 
−
* '''Weeks 5 and 6''' Multirate signal processing. Filterbanks and discrete wavelet transforms. Time domain, frequency domain and polyphase domain representations.
 
−
* '''Week 7 and 8''' 2-Channel orthogonal filterbanks. Iterated filterbanks. Bi-orthogonal filterbanks. Lifting factorizations. Multichannel filterbanks. Modulated filterbanks.
 
−
* '''Weeks 9 and 10''' Multidimensional wavelets. Edgelets, bandlets, ridgelets and other extensions. Lifting for video representation.
 
−
* '''Week 11''' Continuous time wavelets. Series expansions of continuous signals. Haar, Sinc, Meyer, Daubechies and Spline wavelets. Mallat algorithm.
 
−
* '''Weeks 12, 13, 14 and 15''' Applications. Compression. Classification. Graphics. Class Projects.
 
  
−
== Projects ==
+
* F. R. Chung, Spectral graph theory, volume92, AMS Bookstore, 1997.
−
* Project requirements:
+
*D. M. Cvetkovic, P. Rowlinson, and S. Simic,  An introduction to the theory of graph spectra . Cambridge University Press Cambridge, 2010.
−
** Projects should be done individually.
+
*D. K. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on graphs via spectral graph theory.   Applied and Computational Harmonic Analysis , 30(2):129--150,  2011.
−
** Each project must involve using the wavelet transform as a tool. A signal is analyzed/classified, etc by computing its wavelet transform and then the required task (e.g. denoising/classification) is performed in the transform domain.
+
*P. Milanfar.  A tour of modern image filtering: new insights and methods, both  practical and theoretical.   Signal Processing Magazine, IEEE , 30(1):106--128, 2013.
−
** The Matlab toolbox or C libraries can be used for the project. C libraries are available at [http://www.geoffdavis.net/dartmouth/wavelet/wavelet.html Dartmouth] and [http://math.rutgers.edu/%7Eojanen/wavekit/ Rutgers].
+
* S. K. Narang and A. Ortega. Perfect reconstruction two-channel wavelet filter banks for graph  structured data.   Signal Processing, IEEE Transactions on , 60(6):2786--2799,   2012.
−
** Whichever method is used, the source code will have to be made available along with the project report (only for the routines that you write, which could call those available in matlab or C.)
+
* A. Sandryhaila and J. M. Moura. Discrete signal processing on graphs.  IEEE transactions on signal processing , 61(5-8):1644--1656,  2013.
−
*Reporting requirements: a final report and a class presentation.
+
* D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending  high-dimensional data analysis to networks and other irregular domains.  Signal Processing Magazine, IEEE , 30(3):83--98, 2013.
−
* [http://sipi.usc.edu/~ortega/Projects596.html Project descriptions and references]
+
*D. Spielman,  Spectral graph theory, Lecture Notes, Yale University, 2009.
−
* Test data for the projects
 
−
* [http://sipi.usc.edu/~ortega/ee596_wavelet_toolbox.html Software packages]
 
  
−
Demos on the web
+
== Resources ==
−
* [http://www.andrew.cmu.edu/user/jelenak/ Jelena Kovacevic's webpage] contains numerous pointers to books, projects, demos, applets, etc.
 
−
* [http://www.math.sc.edu/%7Esjohnson/wvlib/demo/ Wavelet Library Demo at South Carolina]
 
−
* [http://cm.bell-labs.com/cm/ms/who/wim/cascade/ Bell Labs: Wim Sweldens' Wavelet Cascade Applet]
 
−
* [http://bigwww.epfl.ch/demo/fractsplines/demoprep.html Biomedical Group at EPFL - Fractional Splines Demo]
 
−
* [http://infolab.stanford.edu/IMAGE/ SIMPLIcity Content Based Image Retrieval - Search]
 
−
* [http://www.surveillance-video.com/wavelet-feb-2010.html Wavelet Resources]
 
  
−
== Sample Project Topics  - Organized by Areas ==
+
''[https://lts2.epfl.ch/gsp/ The Graph Signal Processing Toolbox]''
−
* Coding
 
−
** Implementation of a Pyramidal Image Coder
 
−
** Compression of finite-length discrete-time signals using flexible adaptive wavelet packets<
 
−
** Wavelet Descriptors for Planar Curves
 
−
** Sinusoidal Modeling of Audio Signals Using Frame-Based Perceptually Weighted Matching Pursuits
 
−
** Low Complexity Motion Estimation Algorithm for Long-term Memory Motion Compensation Using Hierarchical Motion Estimation
 
−
** Global/Local Motion Compensation for 3D Video Coding Based on Lifting Techniques
 
  
−
* Classification/Recognition
+
== Lectures and Schedule==
−
** Shift Invariant Texture Classification by Using Wavelet Frame
+
* For an outline of topics, see above, detailed listing of topics will be updated throughout the semester.
−
** Texture Feature Extraction with Non-Separable Wavelet Transforms
+
*Lecture 1 (8/25/15)
−
** Comparison of Two Wavelet-Based Image Watermarking Techniques
+
** Introduction: Graph Signal Processing
−
** Application of Wavelet Transform in Analysis of Fractal Signals
+
** Why is the structure of the graph important
−
** Human-Face Detection and Location in Color Images Using Wavelet Decomposition
+
** Examples of graphs in several applications
−
** Music/Speech Classifier using Wavelets
+
*Lecture 2 (8/27/15)
−
** Wavelet Decomposition for the Analysis of Heart Rate Variability
+
** Graphs; Definitions, types of graphs
−
** Wavelet-based fMRI dynamic activation detection
+
** The adjacency matrix and the Laplacian
−
** Wavelet analysis of evoked potentials
+
** Signal variation on a graph and frequency
−
** Detection of Microcalcifications in Mammograms using Wavelet Transforms
+
*Lecture 3 (9/1/15)
−
** Wavelet-based Tone Classification for Thai
+
** Signal variation on a graph and frequency (cont'd)
−
 
+
** Graph Filtering
−
* Denoising
+
*Lecture 4 (9/3/15)
−
** Comparison of Denoising via Block Wiener Filtering in Wavelet Domain with Existing Ad-hoc Linear and Non-linear Denoising Techniques
+
** Linear Algebra Review: spaces, inner products, orthogonality, bases and subspaces
−
** Wavelet-domain filtering of data with Poisson noise
+
*Lecture 5 (9/10/13)
−
** Contrast Enhancement and De-noising using Wavelets
+
** Eigenvalues and eigenvectors -- Interpretation -- Circular convolution
−
** Wavelet Denoising Applied to Time Delay Estimation
+
** Linear Operators based on Polynomials of Adjancency and Laplacian Matrices
−
** Comparison of image denoising using Wavelet Shrinkage vs. MMSE using an exponential decay autocorrelation model
+
** Eigenvectors and Eigenvalues of graphs.
−
** Threshold Denoising Effects on Covariance Matrices
+
*Lecture 6 (9/12/13)
−
** Comparing Performance of Different Wavelet De-noising algorithms with Basic Noise Removal Techniques
+
** Perron-Frobenius Theorem, Rayleigh's Quotient
−
** Information Driven Denosing of MEG data in the Wavelets Domain
+
** Examples
−
** Two Methods for Image Enhancement
+
* '''No lecture on 9/17/13'''
 +
*Lecture 7 (9/19/13)
 +
** Presentation and discussion of graph examples from Homework 1
 +
*Lecture 8 (9/24/13)
 +
** Presentations continued
 +
** Bipartite graphs
 +
** Graph Laplacian, Symmetric Normalized Laplacian, Random Walk Laplacian
 +
*Lecture 9 (9/26/13)
 +
** General bounds on eigenvalues
 +
** Fiedler eigenvector and its application to graph bisection
 +
*Lecture 10 (10/1/13)
 +
** Eigenvalue bounds
 +
** Summary of Graph Laplacians
 +
*Lecture 11 (10/3/13)
 +
** Spectral decomposition of a graph signal: spectral filtering
 +
** Interpretation
 +
** Nodal domains: definition
 +
*Lecture 12 (10/8/13)
 +
** Results on nodal domains
 +
** Vertex domain filtering  
 +
** Polynomials of Graph Laplacian and localized filtering
 +
*Lecture 13 (10/10/13)
 +
** Discussion of IIR, FIR filtering on a graph
 +
** Time frequency localization for regular signals
 +
*Lecture 14 (10/15/13)
 +
** Time frequency localization in Graphs
 +
** Agaskar and Lu (2013)
 +
*Lecture 15 (10/17/13)
 +
** Bounds on Graph Signal Localization
 +
** Motivation of downsampling on graphs
 +
*Lecture 16 (10/22/13)
 +
** Downsampling regular signals
 +
** Results for bipartite graphs
 +
** Open questions 
 +
*Lecture 17 (10/24/13)
 +
** Review for the midterm
 +
*No lecture on 10/29/13
 +
*Midterm  (10/31/13)
 +
*Lecture 18 (11/5/13)
 +
** Introduction to wavelets
 +
** Two channel filterbanks
 +
*Lecture 19 (11/7/13)
 +
** Lifting based solutions
 +
** Time-frequency trade-off, time, frequency localization
 +
*Lecture 20 (11/12/13)
 +
** Multiresolution Analysis
 +
** Diffusion Wavelets
 +
*Lecture 21 (11/14/13)
 +
** Diffusion Wavelets Construction
 +
** Continuous time wavelet transform
 +
*Lecture 22 (11/19/13)
 +
** Spectral Graph Wavelets  
 +
** Graph Filterbanks
 +
*Lecture 23 (11/21/13)
 +
*Lecture 24 (11/26/13)
 +
*Lecture 25 (12/3/13)
 +
*Lecture 26 (12/5/13)
 +
* Project presentations (12/12/13)
  
−
* Watermarking/Halftoning
+
== Projects ==
−
** Introduction of IWT to wavelet-based watermarking and its effect on performance
+
* Individual project requirements: TBD
−
** Inverse Halftoning using Wavelets
 
  
−
* Communications
 
−
** Wavelets Based MC-CDMA System
 
−
** MMSE Estimation Multi-user detection for CDMA System based on Wavelet Transform
 
  
 
== Statement for Students with Disabilities ==
 
== Statement for Students with Disabilities ==
Line 202: Line 202:
 
suspicion of academic dishonesty. The Review process can be found at
 
suspicion of academic dishonesty. The Review process can be found at
 
[http://www.usc.edu/student-affairs/SJACS/ http://www.usc.edu/student-affairs/SJACS/].
 
[http://www.usc.edu/student-affairs/SJACS/ http://www.usc.edu/student-affairs/SJACS/].
 +
 +
== Emergency Preparedness/Course Continuity in a Crisis  ==
 +
In case of a declared emergency if travel to campus is not feasible, USC executive leadership will announce an electronic way for instructors to teach students in their residence halls or homes using a combination of Blackboard, teleconferencing, and other technologies.

Latest revision as of 12:52, 8 October 2015

EE 599, Graph Signal Processing, Fall 2015

Course Description: Theory and applications of emerging tools for signal processing on graphs, including a review of spectral graph theory and newly developed ideas filtering, downsampling, multiresolution decompositions and wavelet transforms"

Prerequisites: EE 483, Introduction to Digital Signal Processing and EE 441, Applied Linear Algebra for Engineering, or equivalent courses. Please note that the course will assume some knowledge of standard DSP concepts as well as of some basic linear algebra. If you took these two courses some time ago it would be a good idea to review some of the key material early in the semester

Background: Graphs have long been used in a wide variety of problems, such analysis of social networks, machine learning, network protocol optimization, decoding of LDPCs or image processing. Techniques based on spectral graph theory provide a "frequency" interpretation of graph data and have proven to be quite popular in many of these applications. In the last few years, a growing amount of work has started extending and complementing spectral graph techniques, leading to the emergence of "Graph Signal Processing" as a broad research field. A common characteristic of this recent work is that it considers the data attached to the vertices as a "graph-signal" and seeks to create new techniques (filtering, sampling, interpolation), similar to those commonly used in conventional signal processing (for audio, images or video), so that they can be applied to these graph signals.

Goals: In this class we provide an overview of this emerging area. The course is aimed at graduate students who have already completed basic coursework in the general areas of signal processing, communications and controls. We start with a review of core concepts, including a review of relevant linear algebra and signal processing concepts. This will be followed by a discussion of advanced topics, focusing on how well established concepts in signal processing are being extended to graph signals (most of this work has taken place in the last 10 years). Finally, we will study specific applications of graph signal processing methods.

Instructor

Antonio Ortega

Signal and Image Processing Institute
Department of Electrical Engineering
University of Southern California
3740 McClintock Ave., EEB 436
Los Angeles, CA 90089-2564

Tel: (213) 740-2320
Fax: (213) 740-4651
Email: antonio DOT ortega AT sipi DOT usc DOT edu

Schedule

  • Lectures Tuesday and Thursday, 11:00am-12:20pm, WPH 106
  • Office hours Tuesday and Thursday, 2-3:30pm, EEB 436, and by appointment.
  • Midterm , Thursday, Nov 5, 11am-12:20pm, in class, room WPH 106.
  • Final There will be no final exam

Grading

Class participation and homework (20%), Midterm (40%), Project (40%). The final project reports will be due on TBD.

Material Covered (Subject to Change)

  • Week 1: Introduction -- Why Graph Signal Processing: concepts, applications and challenges
  • Week 2: Introduction to graph concepts -- Linear algebra review
  • Week 3: Spectral graph theory -- Orthogonal transforms review
  • Week 4:Frequency interpretation -- Nodal Theorems
  • Week 5: Graph filtering -- Vertex and Spectral interpretations
  • Week 6:Advanced Topic 1: Shift invariance, localization and uncertainty principles
  • Week 7: Advanced Topic 2: Downsampling
  • Week 8:Advanced Topic 3: Wavelets
  • Week 9:Advanced Topic 4: Multiresolution and graph approximation
  • Week 10:Advanced Topic 5: Directed Graphs --- Midterm
  • Week 11:Application 1: Image Processing
  • Week 12:Application 2: Sensor Networks
  • Week 13:Application 3: Machine Learning
  • Week 14:Application 4: Finite State Machines
  • Week 15: Project Discussions and Presentations

Texbooks

  • No required textbook. The reference material will include textbooks as well as a number of recent articles

References

Partial list -- more to be added during the semester

  • F. R. Chung, Spectral graph theory, volume92, AMS Bookstore, 1997.
  • D. M. Cvetkovic, P. Rowlinson, and S. Simic, An introduction to the theory of graph spectra . Cambridge University Press Cambridge, 2010.
  • D. K. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis , 30(2):129--150, 2011.
  • P. Milanfar. A tour of modern image filtering: new insights and methods, both practical and theoretical. Signal Processing Magazine, IEEE , 30(1):106--128, 2013.
  • S. K. Narang and A. Ortega. Perfect reconstruction two-channel wavelet filter banks for graph structured data. Signal Processing, IEEE Transactions on , 60(6):2786--2799, 2012.
  • A. Sandryhaila and J. M. Moura. Discrete signal processing on graphs. IEEE transactions on signal processing , 61(5-8):1644--1656, 2013.
  • D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. Signal Processing Magazine, IEEE , 30(3):83--98, 2013.
  • D. Spielman, Spectral graph theory, Lecture Notes, Yale University, 2009.

Resources

The Graph Signal Processing Toolbox

Lectures and Schedule

  • For an outline of topics, see above, detailed listing of topics will be updated throughout the semester.
  • Lecture 1 (8/25/15)
    • Introduction: Graph Signal Processing
    • Why is the structure of the graph important
    • Examples of graphs in several applications
  • Lecture 2 (8/27/15)
    • Graphs; Definitions, types of graphs
    • The adjacency matrix and the Laplacian
    • Signal variation on a graph and frequency
  • Lecture 3 (9/1/15)
    • Signal variation on a graph and frequency (cont'd)
    • Graph Filtering
  • Lecture 4 (9/3/15)
    • Linear Algebra Review: spaces, inner products, orthogonality, bases and subspaces
  • Lecture 5 (9/10/13)
    • Eigenvalues and eigenvectors -- Interpretation -- Circular convolution
    • Linear Operators based on Polynomials of Adjancency and Laplacian Matrices
    • Eigenvectors and Eigenvalues of graphs.
  • Lecture 6 (9/12/13)
    • Perron-Frobenius Theorem, Rayleigh's Quotient
    • Examples
  • No lecture on 9/17/13
  • Lecture 7 (9/19/13)
    • Presentation and discussion of graph examples from Homework 1
  • Lecture 8 (9/24/13)
    • Presentations continued
    • Bipartite graphs
    • Graph Laplacian, Symmetric Normalized Laplacian, Random Walk Laplacian
  • Lecture 9 (9/26/13)
    • General bounds on eigenvalues
    • Fiedler eigenvector and its application to graph bisection
  • Lecture 10 (10/1/13)
    • Eigenvalue bounds
    • Summary of Graph Laplacians
  • Lecture 11 (10/3/13)
    • Spectral decomposition of a graph signal: spectral filtering
    • Interpretation
    • Nodal domains: definition
  • Lecture 12 (10/8/13)
    • Results on nodal domains
    • Vertex domain filtering
    • Polynomials of Graph Laplacian and localized filtering
  • Lecture 13 (10/10/13)
    • Discussion of IIR, FIR filtering on a graph
    • Time frequency localization for regular signals
  • Lecture 14 (10/15/13)
    • Time frequency localization in Graphs
    • Agaskar and Lu (2013)
  • Lecture 15 (10/17/13)
    • Bounds on Graph Signal Localization
    • Motivation of downsampling on graphs
  • Lecture 16 (10/22/13)
    • Downsampling regular signals
    • Results for bipartite graphs
    • Open questions
  • Lecture 17 (10/24/13)
    • Review for the midterm
  • No lecture on 10/29/13
  • Midterm (10/31/13)
  • Lecture 18 (11/5/13)
    • Introduction to wavelets
    • Two channel filterbanks
  • Lecture 19 (11/7/13)
    • Lifting based solutions
    • Time-frequency trade-off, time, frequency localization
  • Lecture 20 (11/12/13)
    • Multiresolution Analysis
    • Diffusion Wavelets
  • Lecture 21 (11/14/13)
    • Diffusion Wavelets Construction
    • Continuous time wavelet transform
  • Lecture 22 (11/19/13)
    • Spectral Graph Wavelets
    • Graph Filterbanks
  • Lecture 23 (11/21/13)
  • Lecture 24 (11/26/13)
  • Lecture 25 (12/3/13)
  • Lecture 26 (12/5/13)
  • Project presentations (12/12/13)

Projects

  • Individual project requirements: TBD


Statement for Students with Disabilities

Any student requesting academic accommodations based on a disability is required to register with Disability Services and Programs (DSP) each semester. A letter of verification for approved accommodations can be obtained from DSP. Please be sure the letter is delivered to me (or to TA) as early in the semester as possible. DSP is located in STU 301 and is open 8:30 a.m.--5:00 p.m., Monday through Friday. The phone number for DSP is (213) 740-0776.


Statement on Academic Integrity

USC seeks to maintain an optimal learning environment. General principles of academic honesty include the concept of respect for the intellectual property of others, the expectation that individual work will be submitted unless otherwise allowed by an instructor, and the obligations both to protect oneís own academic work from misuse by others as well as to avoid using anotherís work as oneís own. All students are expected to understand and abide by these principles. Scampus, the Student Guidebook, contains the Student Conduct Code in Section 11.00, while the recommended sanctions are located in Appendix A http://www.usc.edu/dept/publications/SCAMPUS/gov/

Students will be referred to the Office of Student Judicial Affairs and Community Standards for further review, should there be any suspicion of academic dishonesty. The Review process can be found at http://www.usc.edu/student-affairs/SJACS/.

Emergency Preparedness/Course Continuity in a Crisis

In case of a declared emergency if travel to campus is not feasible, USC executive leadership will announce an electronic way for instructors to teach students in their residence halls or homes using a combination of Blackboard, teleconferencing, and other technologies.

Retrieved from "https://biron.usc.edu/wiki/index.php?title=EE_599_Graph_Signal_Processing&oldid=2878"