# Difference between revisions of "EE 599 Graph Signal Processing"

m |
m (→Texbooks) |
||

Line 71: | Line 71: | ||

== Texbooks == | == Texbooks == | ||

* No required textbook. The reference material will include textbooks as well as a number of recent articles | * 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. | ||

== Lectures and Schedule== | == Lectures and Schedule== |

## Revision as of 17:16, 6 August 2013

## Contents

- 1 EE 599, Graph Signal Processing, Fall 2013
- 2 Instructor
- 3 Schedule
- 4 Grading
- 5 Material Covered (Subject to Change)
- 6 Texbooks
- 7 References
- 8 Lectures and Schedule
- 9 Projects
- 10 Statement for Students with Disabilities
- 11 Statement on Academic Integrity
- 12 Emergency Preparedness/Course Continuity in a Crisis

## EE 599, Graph Signal Processing, Fall 2013

**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

*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, 3:30-4:50pm, GFS 220**Office hours**Tuesday and Thursday, 5-6pm, EEB 436, and by appointment.**Midterm**, 10/31/13 in class**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 Dec 13, 2013.

## 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.

## Lectures and Schedule

- For an outline of topics, see above, detailed listing of topics will be updated throughout the semester.
- Lecture 1 (8/27/13)
- Introduction

- Lecture 2 (8/29/13)
- Lecture 3 (9/3/13)
- Lecture 4 (9/5/13)
- Lecture 5 (9/10/13)
- Lecture 6 (9/12/13)
- No lecture on 9/17/13
- Lecture 7 (9/19/13)
- Lecture 8 (9/24/13)
- Lecture 9 (9/26/13)
- Lecture 10 (10/1/13)
- Lecture 11 (10/3/13)
- Lecture 12 (10/8/13)
- Lecture 13 (10/10/13)
- Lecture 14 (10/15/13)
- Lecture 15 (10/17/13)
- Lecture 16 (10/22/13)
- Lecture 17 (10/24/13)
- No lecture on 10/29/13
- Midterm (10/31/13)
- Lecture 18 (11/5/13)
- Lecture 19 (11/7/13)
- Lecture 20 (11/12/13)
- Lecture 21 (11/14/13)
- Lecture 22 (11/19/13)
- Lecture 23 (11/21/13)
- Lecture 24 (12/3/13)
- Lecture 25 (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.