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

m (→EE 599, Graph Signal Processing, Fall 2013) |
m (→EE 599, Graph Signal Processing, Fall 2013) |
||

Line 4: | Line 4: | ||

'''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 | analysis of social networks, machine learning, network protocol | ||

optimization, decoding of LDPCs or image processing. Techniques based | optimization, decoding of LDPCs or image processing. Techniques based | ||

− | on spectral graph theory provide a | + | on spectral graph theory provide a "frequency" interpretation of graph |

data and have proven to be quite popular in many of these | data and have proven to be quite popular in many of these | ||

applications. | applications. | ||

In the last few years, a growing amount of work has started extending | In the last few years, a growing amount of work has started extending | ||

and complementing spectral graph techniques, leading to the emergence | and complementing spectral graph techniques, leading to the emergence | ||

− | of | + | of "Graph Signal Processing" as a broad research field. A common |

characteristic of this recent work is that it considers the data | characteristic of this recent work is that it considers the data | ||

− | attached to the vertices as a | + | attached to the vertices as a "graph-signal" and seeks to create new |

techniques (filtering, sampling, interpolation), similar to those | techniques (filtering, sampling, interpolation), similar to those | ||

commonly used in conventional signal processing (for audio, images or | commonly used in conventional signal processing (for audio, images or | ||

video), so that they can be applied to these graph signals. | video), so that they can be applied to these graph signals. | ||

− | '''Goals:''' | + | '''Goals:''' In this class we provide an overview of this emerging area. The course |

is aimed at graduate students who have already completed basic | is aimed at graduate students who have already completed basic | ||

coursework in the general areas of signal processing, communications | coursework in the general areas of signal processing, communications |

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

## Contents

## 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, 11-12:20pm, KAP 147**Office hours**Tuesday and Thursday, 1:30-3:30pm, EEB 436, and by appointment.**Midterm 1**Tuesday Oct 23, 2012, in class**Midterm 2**Thursday Nov 15, 2012, in class**Final**There will be no final exam

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

## Lectures

- Lecture 1 (8/28/12)
- Introduction, goals, historical perspective

- Lecture 2 (8/30/12)
- Uncertainty principle
- Practical time frequency localization example
- Signal spaces

- Lecture 3 (9/4/12)
- Piecewise constant signals and Haar Wavelets
- Bases
- Norms

- Lecture 4 (9/6/12)
- View lectures 1-4 from 2010

- 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

**Required:**

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

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

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

- Project requirements:
- Projects should be done individually.
- 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.
- The Matlab toolbox or C libraries can be used for the project. C libraries are available at Dartmouth and Rutgers.
- 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.)

- Reporting requirements: a final report and a class presentation.
- Project descriptions and references
- Test data for the projects
- Software packages

Demos on the web

- Jelena Kovacevic's webpage contains numerous pointers to books, projects, demos, applets, etc.
- Wavelet Library Demo at South Carolina
- Bell Labs: Wim Sweldens' Wavelet Cascade Applet
- Biomedical Group at EPFL - Fractional Splines Demo
- SIMPLIcity Content Based Image Retrieval - Search
- Wavelet Resources

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