Abstract:
We consider the problem of signal recovery on graphs. Graphs model data with complex structure as signals on a graph. Graph signal recovery recovers one or multiple smoot...Show MoreMetadata
Abstract:
We consider the problem of signal recovery on graphs. Graphs model data with complex structure as signals on a graph. Graph signal recovery recovers one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We formulate graph signal recovery as an optimization problem, for which we provide a general solution through the alternating direction methods of multipliers. We show how signal inpainting, matrix completion, robust principal component analysis, and anomaly detection all relate to graph signal recovery and provide corresponding specific solutions and theoretical analysis. We validate the proposed methods on real-world recovery problems, including online blog classification, bridge condition identification, temperature estimation, recommender system for jokes, and expert opinion combination of online blog classification.
Published in: IEEE Transactions on Signal Processing ( Volume: 63, Issue: 17, September 2015)
Funding Agency:
Department of Electrical and Computer Engineering
Siheng Chen (S’13) received his B. Eng degree in Optoelectronics Engineering in 2011 from the Beijing Institute of Technology and the M.S. degree in Electrical and Computer Engineering in 2012 from Carnegie Mellon University. He is currently a Ph.D. student in Electrical and Computer Engineering and a secondary master student in Machine Learning at Carnegie Mellon University. His research interests include signal processi...Show More
Siheng Chen (S’13) received his B. Eng degree in Optoelectronics Engineering in 2011 from the Beijing Institute of Technology and the M.S. degree in Electrical and Computer Engineering in 2012 from Carnegie Mellon University. He is currently a Ph.D. student in Electrical and Computer Engineering and a secondary master student in Machine Learning at Carnegie Mellon University. His research interests include signal processi...View more
Aliaksei Sandryhaila (S’06–M’10) received a B.S. degree in Computer Science from Drexel University, Philadelphia, PA, in 2005, and a Ph.D. degree in Electrical and Computer Engineering from Carnegie Mellon University (CMU), Pittsburgh, PA, in 2010. He is currently with HP Vertica, where he develops tools for Big Data analysis. Previously, he was a Research Scientist in the Department of Electrical and Computer Engineering...Show More
Aliaksei Sandryhaila (S’06–M’10) received a B.S. degree in Computer Science from Drexel University, Philadelphia, PA, in 2005, and a Ph.D. degree in Electrical and Computer Engineering from Carnegie Mellon University (CMU), Pittsburgh, PA, in 2010. He is currently with HP Vertica, where he develops tools for Big Data analysis. Previously, he was a Research Scientist in the Department of Electrical and Computer Engineering...View more
Department of Electrical and Computer Engineering
José M. F. Moura (S’71–M’75–SM’90–F’94) is the Philip L. and Marsha Dowd University Professor at Carnegie Mellon University (CMU). He received the Engenheiro Electrotécnico degree from Instituto Superior Técnico (IST), Lisbon, Portugal, and the M.Sc., E.E., and D.Sc. degrees in EECS from MIT, Cambridge, MA. He was on the faculty at IST and a visiting Professor at MIT and NYU. He is founding director of ICTI@CMU, a large e...Show More
José M. F. Moura (S’71–M’75–SM’90–F’94) is the Philip L. and Marsha Dowd University Professor at Carnegie Mellon University (CMU). He received the Engenheiro Electrotécnico degree from Instituto Superior Técnico (IST), Lisbon, Portugal, and the M.Sc., E.E., and D.Sc. degrees in EECS from MIT, Cambridge, MA. He was on the faculty at IST and a visiting Professor at MIT and NYU. He is founding director of ICTI@CMU, a large e...View more
Department of Electrical and Computer Engineering
Jelena Kovačević (S’88–M’91–SM’96–F’02) received the Dipl. Electr. Eng. degree from the EE Department, University of Belgrade, Yugoslavia, in 1986, and the M.S. and Ph.D. degrees from Columbia University, New York, in 1988 and 1991, respectively. From 1991–2002, she was with Bell Labs, Murray Hill, NJ. She was a co-founder and Technical VP of xWaveforms, based in New York City and an Adjunct Professor at Columbia Universi...Show More
Jelena Kovačević (S’88–M’91–SM’96–F’02) received the Dipl. Electr. Eng. degree from the EE Department, University of Belgrade, Yugoslavia, in 1986, and the M.S. and Ph.D. degrees from Columbia University, New York, in 1988 and 1991, respectively. From 1991–2002, she was with Bell Labs, Murray Hill, NJ. She was a co-founder and Technical VP of xWaveforms, based in New York City and an Adjunct Professor at Columbia Universi...View more
Contents Department of Electrical and Computer Engineering
Siheng Chen (S’13) received his B. Eng degree in Optoelectronics Engineering in 2011 from the Beijing Institute of Technology and the M.S. degree in Electrical and Computer Engineering in 2012 from Carnegie Mellon University. He is currently a Ph.D. student in Electrical and Computer Engineering and a secondary master student in Machine Learning at Carnegie Mellon University. His research interests include signal processing, machine learning, and data mining.
Siheng Chen (S’13) received his B. Eng degree in Optoelectronics Engineering in 2011 from the Beijing Institute of Technology and the M.S. degree in Electrical and Computer Engineering in 2012 from Carnegie Mellon University. He is currently a Ph.D. student in Electrical and Computer Engineering and a secondary master student in Machine Learning at Carnegie Mellon University. His research interests include signal processing, machine learning, and data mining.View more
Aliaksei Sandryhaila (S’06–M’10) received a B.S. degree in Computer Science from Drexel University, Philadelphia, PA, in 2005, and a Ph.D. degree in Electrical and Computer Engineering from Carnegie Mellon University (CMU), Pittsburgh, PA, in 2010. He is currently with HP Vertica, where he develops tools for Big Data analysis. Previously, he was a Research Scientist in the Department of Electrical and Computer Engineering at CMU and a Senior Research Scientist at SpiralGen, Inc. His research interests include large-scale data analysis, signal processing, machine learning, high-performance computing, and fast algorithm design and optimization.
Aliaksei Sandryhaila (S’06–M’10) received a B.S. degree in Computer Science from Drexel University, Philadelphia, PA, in 2005, and a Ph.D. degree in Electrical and Computer Engineering from Carnegie Mellon University (CMU), Pittsburgh, PA, in 2010. He is currently with HP Vertica, where he develops tools for Big Data analysis. Previously, he was a Research Scientist in the Department of Electrical and Computer Engineering at CMU and a Senior Research Scientist at SpiralGen, Inc. His research interests include large-scale data analysis, signal processing, machine learning, high-performance computing, and fast algorithm design and optimization.View more
Department of Electrical and Computer Engineering
José M. F. Moura (S’71–M’75–SM’90–F’94) is the Philip L. and Marsha Dowd University Professor at Carnegie Mellon University (CMU). He received the Engenheiro Electrotécnico degree from Instituto Superior Técnico (IST), Lisbon, Portugal, and the M.Sc., E.E., and D.Sc. degrees in EECS from MIT, Cambridge, MA. He was on the faculty at IST and a visiting Professor at MIT and NYU. He is founding director of ICTI@CMU, a large education and research program between CMU and Portugal, www.cmuportugal.org. His research interests are on data science and include statistical, algebraic, and distributed signal and image processing on graphs. He has published over 550 papers, has twelve patents issued by the US Patent Office, and cofounded SpiralGen.
Dr. Moura is the 2016 IEEE Vice-President of Technical Activities. He served as IEEE Division IX Director and IEEE Board Director and on several IEEE Boards. He was President of the IEEE Signal Processing Society (SPS), served as Editor in Chief for the IEEE Transactions in Signal Processing, interim Editor in Chief for the IEEE Signal Processing Letters, and member of several Editorial Boards, including IEEE Proceedings, IEEE Signal Processing Magazine, and the ACM Transactions on Sensor Networks.
Dr. Moura is member of the U.S. National Academy of Engineering, Fellow of the U.S. National Academy of Inventors, corresponding member of the Academy of Sciences of Portugal, and Fellow of the AAAS. He received the IEEE Signal Processing Society Technical Achievement Award and the IEEE Signal Processing Society Award.
José M. F. Moura (S’71–M’75–SM’90–F’94) is the Philip L. and Marsha Dowd University Professor at Carnegie Mellon University (CMU). He received the Engenheiro Electrotécnico degree from Instituto Superior Técnico (IST), Lisbon, Portugal, and the M.Sc., E.E., and D.Sc. degrees in EECS from MIT, Cambridge, MA. He was on the faculty at IST and a visiting Professor at MIT and NYU. He is founding director of ICTI@CMU, a large education and research program between CMU and Portugal, www.cmuportugal.org. His research interests are on data science and include statistical, algebraic, and distributed signal and image processing on graphs. He has published over 550 papers, has twelve patents issued by the US Patent Office, and cofounded SpiralGen.
Dr. Moura is the 2016 IEEE Vice-President of Technical Activities. He served as IEEE Division IX Director and IEEE Board Director and on several IEEE Boards. He was President of the IEEE Signal Processing Society (SPS), served as Editor in Chief for the IEEE Transactions in Signal Processing, interim Editor in Chief for the IEEE Signal Processing Letters, and member of several Editorial Boards, including IEEE Proceedings, IEEE Signal Processing Magazine, and the ACM Transactions on Sensor Networks.
Dr. Moura is member of the U.S. National Academy of Engineering, Fellow of the U.S. National Academy of Inventors, corresponding member of the Academy of Sciences of Portugal, and Fellow of the AAAS. He received the IEEE Signal Processing Society Technical Achievement Award and the IEEE Signal Processing Society Award.View more
Department of Electrical and Computer Engineering
Jelena Kovačević (S’88–M’91–SM’96–F’02) received the Dipl. Electr. Eng. degree from the EE Department, University of Belgrade, Yugoslavia, in 1986, and the M.S. and Ph.D. degrees from Columbia University, New York, in 1988 and 1991, respectively. From 1991–2002, she was with Bell Labs, Murray Hill, NJ. She was a co-founder and Technical VP of xWaveforms, based in New York City and an Adjunct Professor at Columbia University. In 2003, she joined Carnegie Mellon University, where she is Schramm Professor and Head of Electrical and Computer Engineering, Professor of Biomedical Engineering, and was the Director of the Center for Bioimage Informatics at Carnegie Mellon University. Her research interests include wavelets, frames, graphs, and applications to bioimaging and smart infrastructure.
Dr. Kovačević coauthored the books Wavelets and Subband Coding (Prentice Hall, 1995) and Foundations of Signal Processing (Cambridge University Press, 2014), a top-10 cited paper in the Journal of Applied and Computational Harmonic Analysis, and the paper for which A. Mojsilovic received the Young Author Best Paper Award. Her paper on multidimensional filter banks and wavelets was selected as one of the Fundamental Papers in Wavelet Theory. She received the Belgrade October Prize in 1986, the E. I. Jury Award at Columbia University in 1991 and the 2010 CIT Philip L. Dowd Fellowship Award from the College of Engineering at Carnegie Mellon University. She is a past Editor-in-Chief of the IEEE Transactions on Image Processing, served as a guest co-editor on a number of special issues and is/was on the editorial boards of several journals. She was a regular member of the NIH Microscopic Imaging Study Section and served as a Member-at-Large of the IEEE Signal Processing Society Board of Governors. She is a past Chair of the IEEE Signal Processing Society Bio Imaging and Signal Processing Technical Committee. She has been involved in organizing numerous conferences. She was a plenary/keynote speaker at a number of international conferences and meetings.
Jelena Kovačević (S’88–M’91–SM’96–F’02) received the Dipl. Electr. Eng. degree from the EE Department, University of Belgrade, Yugoslavia, in 1986, and the M.S. and Ph.D. degrees from Columbia University, New York, in 1988 and 1991, respectively. From 1991–2002, she was with Bell Labs, Murray Hill, NJ. She was a co-founder and Technical VP of xWaveforms, based in New York City and an Adjunct Professor at Columbia University. In 2003, she joined Carnegie Mellon University, where she is Schramm Professor and Head of Electrical and Computer Engineering, Professor of Biomedical Engineering, and was the Director of the Center for Bioimage Informatics at Carnegie Mellon University. Her research interests include wavelets, frames, graphs, and applications to bioimaging and smart infrastructure.
Dr. Kovačević coauthored the books Wavelets and Subband Coding (Prentice Hall, 1995) and Foundations of Signal Processing (Cambridge University Press, 2014), a top-10 cited paper in the Journal of Applied and Computational Harmonic Analysis, and the paper for which A. Mojsilovic received the Young Author Best Paper Award. Her paper on multidimensional filter banks and wavelets was selected as one of the Fundamental Papers in Wavelet Theory. She received the Belgrade October Prize in 1986, the E. I. Jury Award at Columbia University in 1991 and the 2010 CIT Philip L. Dowd Fellowship Award from the College of Engineering at Carnegie Mellon University. She is a past Editor-in-Chief of the IEEE Transactions on Image Processing, served as a guest co-editor on a number of special issues and is/was on the editorial boards of several journals. She was a regular member of the NIH Microscopic Imaging Study Section and served as a Member-at-Large of the IEEE Signal Processing Society Board of Governors. She is a past Chair of the IEEE Signal Processing Society Bio Imaging and Signal Processing Technical Committee. She has been involved in organizing numerous conferences. She was a plenary/keynote speaker at a number of international conferences and meetings.View more
