Low-Rank Models in Visual Analysis: Theories, Algorithms, and Applications

By Zhouchen Lin and Hongyang Zhang

Low-Rank Models in Visual Analysis: Theories, Algorithms, and Applications presents the state-of-the-art on low-rank models and their application to visual analysis. It provides insight into the ideas behind the models and their algorithms, giving details of their formulation and deduction. The main applications included are video denoising, background modeling, image alignment and rectification, motion segmentation, image segmentation and image saliency detection. Readers will learn which Low-rank models are highly useful in practice (both linear and nonlinear models), how to solve low-rank models efficiently, and how to apply low-rank models to real problems.

• Presents a self-contained, up-to-date introduction that covers underlying theory, algorithms and the state-of-the-art in current applications
• Provides a full and clear explanation of the theory behind the models
• Includes detailed proofs in the appendices

• Language: English
• Publisher: Academic Press
• Release date: Jun 6, 2017
• ISBN: 9780128127322

Zhouchen Lin

Zhouchen Lin received the Ph.D. degree in applied mathematics from Peking University in 2000. He is currently a Professor at Key Laboratory of Machine Perception (MOE), School of Electronics Engineering and Computer Science, Peking University. His research areas include computer vision, image processing, machine learning, pattern recognition, and numerical optimization. He is an area chair of CVPR 2014/2016, ICCV 2015 and NIPS 2015 and a senior program committee member of AAAI 2016/2017 and IJCAI 2016. He is an associate editor of IEEE Trans. Pattern Analysis and Machine Intelligence and International J. Computer Vision. He is an IAPR fellow.

Book preview

Low-Rank Models in Visual Analysis

Theories, Algorithms and Applications

First edition

Zhouchen Lin

Peking University, School of Electronics Engineering and Computer Science, Beijing, PR China

Hongyang Zhang

Carnegie Mellon University, School of Computer Science, Pittsburgh, USA

Table of Contents

Cover image

Title page

Copyright

About the Authors

Preface

Acknowledgment

Notations

Chapter 1: Introduction

Abstract

References

Chapter 2: Linear Models

Abstract

2.1. Single Subspace Models

2.2. Multi-Subspace Models

2.3. Theoretical Analysis

References

Chapter 3: Nonlinear Models

Abstract

3.1. Kernel Methods

3.2. Laplacian Based Methods

3.3. Locally Linear Representation

3.4. Transformation Invariant Clustering

References

Chapter 4: Optimization Algorithms

Abstract

4.1. Convex Algorithms

4.2. Nonconvex Algorithms

4.3. Randomized Algorithms

References

Chapter 5: Representative Applications

Abstract

5.1. Video Denoising [19]

5.2. Background Modeling [2]

5.3. Robust Alignment by Sparse and Low-Rank (RASL) Decomposition [42]

5.4. Transform Invariant Low-Rank Textures (TILT) [58]

5.5. Motion and Image Segmentation [4,29,30]

5.6. Image Saliency Detection [21]

5.7. Partial-Duplicate Image Search [54]

5.8. Image Tag Completion and Refinement [15]

5.9. Other Applications

References

Chapter 6: Conclusions

Abstract

6.1. Low-Rank Models for Tensorial Data

6.2. Nonlinear Manifold Clustering

6.3. Randomized Algorithms

References

Appendix A: Proofs

Abstract

A.1. Proof of Theorem 2.6 [29]

A.2. Proof of Theorem 2.7 [29]

A.3. Proof of Theorem 2.8 [29]

A.4. Proof of Theorem 2.10 [30]

A.5. Proof of Theorem 2.11 [30]

A.6. Proof of Theorem 2.12 [30]

A.7. Proof of Theorem 2.13 [30]

A.8. Proof of Theorem 2.14 [19]

A.9. Proof of Theorem 2.15

A.10. Proof of Theorem 2.16 [8]

A.11. Proof of Theorem 2.17 [8]

A.12. Proof of Theorem 2.18

A.13. Proof of Theorem 2.19 [27]

A.14. Proof of Theorem 2.20 [27]

A.15. Proof of Theorem 2.21 [27]

A.16. Proof of Theorem 2.22 [20]

A.17. Proof of Theorem 4.2 [2]

A.18. Proof of Theorem 4.4 [15]

A.19. Proof of Theorem 4.5 [16]

A.20. Proof of Theorem 4.6 [16]

A.21. Proofs of Proposition 4.2 and Theorem 4.7 [18]

A.22. Proof of Theorem 4.8 [17]

A.23. Proof of Theorem 4.9 [17]

A.24. Proof of Theorem 4.16 [21]

A.25. Proof of Theorem 4.17 [21]

A.26. Proof of Theorem 4.18 [25]

A.27. Proof of Theorem 4.19 [28]

A.28. Proof of Theorem 4.21 [1]

A.29. Proof of Theorem 4.22 [1]

References

Appendix B: Mathematical Preliminaries

Abstract

B.1. Terminologies

B.2. Basic Results

References

Index

Copyright

Academic Press is an imprint of Elsevier

125 London Wall, London EC2Y 5AS, United Kingdom

525 B Street, Suite 1800, San Diego, CA 92101-4495, United States

50 Hampshire Street, 5th Floor, Cambridge, MA 02139, United States

The Boulevard, Langford Lane, Kidlington, Oxford OX5 1GB, United Kingdom

Copyright © 2017 Elsevier Ltd. All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher's permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.

This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).

Notices

Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.

Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.

To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library

ISBN: 978-0-12-812731-5

For information on all Academic Press publications visit our website at https://www.elsevier.com/books-and-journals

Publisher: Mara E. Conner

Acquisition Editor: Tim Pitts

Editorial Project Manager: Anna Valutkevich

Production Project Manager: Mohanapriyan Rajendran

Cover Designer: Matthew Limbert

Typeset by VTeX

About the Authors

Zhouchen Lin received the Ph.D. degree in applied mathematics from Peking University in 2000. He is currently a Professor at Key Laboratory of Machine Perception (Ministry of Education), School of Electronics Engineering and Computer Science, Peking University. His research areas include computer vision, image processing, machine learning, pattern recognition, and numerical optimization. He is an area chair of CVPR 2014/2016, ICCV 2015 and NIPS 2015 and a senior program committee member of AAAI 2016/2017/2018 and IJCAI 2016. He is an associate editor of IEEE Transactions on Pattern Analysis and Machine Intelligence and International Journal of Computer Vision. He is an IAPR fellow.

Hongyang Zhang received the Master's degree in computer science from Peking University, Beijing, China in 2015. He is now a Ph.D. candidate in Machine Learning Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, USA. His research areas broadly include machine learning, statistics, and optimization.

Preface

Zhouchen Lin     Peking University

Hongyang Zhang     Carnegie Mellon University

Sparse representation and compressed sensing have achieved tremendous success in practice. They naturally fit for order-one signals, such as voices and feature vectors. However, in applications we often encounter various types of data, such as images, videos, and DNA microarrays. They are inherently matrices or even tensors. Then we are naturally faced with a question: how to measure the sparsity of matrices and tensors? Low-rank models are recent tools that can robustly and efficiently handle high-dimensional data, due to the fact that many types of data (raw or after some nonlinear transforms) reside near (single or multiple) subspaces. The surge of low-rank models in recent years was inspired by sparse representation and compressed sensing, where rank is interpreted as the measure of the second order (i.e., matrix) sparsity, rather than merely a mathematical concept. There has been systematic development on new theories, algorithms, and applications. In this monograph, based on our own work we review part of the recent development on low-rank models. We will show the basic theories and algorithms of low-rank models and their various applications in visual data analysis, such as video denoising, background modeling, image alignment and rectification, motion segmentation, image segmentation, and image saliency detection, to name just a few. Actually, low-rank models can also be applied to other types of data, such as voice, music, and DNA microarrays. All these applications testify to the usefulness of low-rank models and explain why low-rank models have attracted so much attention in the past years. So we expect that the research community needs an up-to-date and relatively self-contained monograph on this topic. This monograph is mainly intended for researchers in industries and teachers and graduate students in universities, who are interested in using low-rankness as a regularizer to build mathematical models for their problems or who are working on data with high noise or even severe corruption. It should be very easy for new researchers to master the state-of-the-arts and start their own research problems, no matter they are theorists or engineers. Due to our limited knowledge and time and fast growing of the literature, we are unable to provide the complete picture of the whole area. Other related monographs include:

• Y. Fu. Low-Rank and Sparse Modeling for Visual Analysis. Springer, 2014.

• O. Oreifej and M. Shah. Robust Subspace Estimation Using Low-Rank Optimization: Theory and Applications. Springer, 2014.

• T. Bouwmans, N. S. Aybat, and E.-h. Zahzah. Handbook of Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing. Chapman and Hall/CRC, 2016.

There is also an excellent review on low-rank models for image analysis:

• X. Zhou, C. Yang, H. Zhao and W. Yu. Low-rank modeling and its applications in image analysis. ACM Computing Surveys, 47(2), Article No. 36, 2015.

Different from them, this monograph may serve as a textbook for graduate students majoring in image processing, computer vision, machine learning, data science, etc. The following is also an excellent textbook:

• R. Vidal, Y. Ma, and S. S. Sastry. Generalized Principal Component Analysis. Springer, 2016.

But it is less focused on low-rank models.

Enjoy reading!

March 31, 2017

Acknowledgment

Zhouchen Lin     

Hongyang Zhang     

We thank our collaborators, Maria-Florina Balcan, Jiashi Feng, Yifan Fu, Junbin Gao, Yuqing Hou, Han Hu, Baohua Li, Chun-Guang Li, Huan Li, Qi Li, Zhizhong Li, Yang Lin, Guangcan Liu, Risheng Liu, Canyi Lu, Jianjun Qian, Xiang Ren, Chen Xu, Shuicheng Yan, Li Yang, Ming Yin, Xin Zhang, Pan Zhou, Liansheng Zhuang, Wangmeng Zuo and others, for their significant contributions to our joint work on various aspects of low-rank modeling. We also thank John Wright, Yi Ma, and René Vidal for valuable communications and Tim Pitts at Elsevier for encouraging and assisting the publication of this monograph. This monograph is supported by National Natural Science Foundation of China under Grant Nos. 61625301 and 61272341 and the National Basic Research Program of China (973 Program) under Grant No. 2015CB352502. Finally, we would like to thank our family members for their great support. With them beside us, the life becomes so easy and the work becomes so efficient. Without them, this book will not be written.

March 31, 2017

Notations

Bold capital A matrix.

Bold lowercase A vector.

Calligraphic capital A tensor, a subspace, an operator, or a set.

 Set of real numbers, set of nonnegative real numbers.

 Probability of event x.

 Expectation of event x.

.

 Size of data matrix D.

.

 Grows in the same order of n.

 Grows no faster than the order of n.

⊗ Tensor product.

⊕ Direct sum of subspaces.

 Vector whose i-th entry is 1 and others are 0's.

 The identity matrix, all-zero matrix or vector, and all-one vector.

D Noisy data matrix.

 Clean data matrix.

 Noise matrix.

 Optimal solution to a certain optimization problem.

 The j-th column of matrix D.

 The entry at the i-th row and the j-th column of D.

 Subsampling the rows of D whose indices are in Ω.

 Subsampling the columns of D whose indices are in Ω.

 Transpose of matrix D.

 Moore–Penrose pseudo-inverse of matrix D.

 Vector whose entries are diagonal entries of matrix D.

 Diagonal matrix whose diagonal entries are entries of vector d.

 Range space of columns of D.

 The i-th largest singular value of matrix D.

 The i-th largest eigenvalue of matrix D.

.

 Operator norm of an operator or a matrix.

.

 Nuclear norm of matrices, the sum of singular values.

 Schatten ppseudo-norm of the vector of singular values.

pseudo-norm, number of nonzero entries.

pseudo-norm of matrices, number of nonzero columns.

.

.

.

.

.

.

.

∂f Subgradient (resp. supergradient) of a convex (resp. concave) function f.

.

.

.

, sum of the column space and the row space.

.

.

.

.

.

.

.

.

 Proximal operator w.r.t. f and parameter α.

 Bernoulli distribution with parameter p.

 Gaussian distribution with mean a .

 Uniform distribution on the set of subsets of cardinality k.

Chapter 1

Introduction

Abstract

This chapter gives the background of low-rank modeling, i.e., modeling the phenomenon of data distributing around low-dimensional manifolds, extending the traditional sparse representation and compressed sensing theories by using rank as the regularizer, and why using rank is appropriate. It also gives a brief guideline to the content of the monograph.

Keywords

Low-dimensional manifold; Principal Component Analysis; Manifold learning; Rank; Sparsity; Compressed sensing; Sparse representation

In practice, many kinds of data distribute around low-dimensional manifolds, although they are in high-dimensional spaces. Such a phenomenon is evidenced by the effectiveness of Principal Component Analysis (PCA) where the number of principal components can be much smaller than the data dimension [5]. This phenomenon is also utilized in manifold learning where manifolds can be nonlinear [6]. In this scenario, low dimensionality plays the central role. It is known that dimension is closely related to rank, e.g., the dimension of a subspace equals the rank of the data matrix whose columns are sufficient samples on the subspace. So using rank as a mathematical tool will be helpful in studying the low-dimensional structures in data distribution.

Another motivation of using rank in data and signal analysis is from sparse representation and compressed sensing [3,4,9]. These approaches have achieved tremendous success in practice [1]. However, they are mainly studied in the context of order-one data, such as voices and feature vectors. The corresponding sparsity measure is the number of nonzero entries in the data vector or the representation vector, which we call the first order sparsity. In reality, we are also frequently faced with higher order data, such as images, videos, and DNA microarrays, which can be modeled as matrices or even tensors. The traditional sparse representation and compressed sensing theories may be applied to these kinds of data. But there are many cases that they may fail or are less effective. For example, in the Netflix challenge¹ (Fig. 1.1), to infer the unknown user ratings on movies, one has to consider both the correlation between users and the correlation between movies. When compressing or inpainting images and videos, we have to fully utilize the spatial and temporal correlation in images or video frames. It is also known that the correlation among rows and columns of a matrix is closely related to the rank of the matrix. So it will also be advantageous if rank is considered as a regularizer when processing high-order data.

Figure 1.1 The Netflix challenge is to predict the unknown ratings of users on movies.

Actually, like sparsity, the rank constraint has appeared in the literature prior to its recent popularity, e.g., reduced rank regression (RRR) in statistics [8] and matrix factorization in data processing [2]. In three-dimensional stereo vision [7], rank constraints are ubiquitous. The popularity of sparse representation and compressed sensing further inspires the study on low-rank models, as an extension to the traditional vector-based theories. In this context, rank is interpreted as the measure of the second order (i.e., matrix) sparsity. It turns out that low-rank models are robust and effective in combating outliers and missing values.

In this monograph, based on our own work we review a part of the recent development on low-rank models. We first introduce linear models in Chapter 2, where the models are classified as the single subspace models and the multi-subspace ones. We then review the nonlinear models in Chapter 3. We further introduce in Chapter 4 the commonly used optimization algorithms for solving low-rank models, which are classified as convex, non-convex, and randomized ones. Next, we review some representative applications in Chapter 5. Finally, we conclude the book in Chapter 6.

References

[1] E. Candès, M. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine 2008;25(2):21–30.

[2] A. Cichocki, R. Zdunek, A.H. Phan, S. Amari, Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-Way Data Analysis and Blind Source Separation. John Wiley & Sons; 2009.

[3] M. Elad, Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer; 2010.

[4] S. Foucart, H. Rauhut, A Mathematical Introduction to Compressive Sensing. Springer; 2013.

[5] I. Jolliffe, Principal Component Analysis. Springer; 1986.

[6] J.A. Lee, M. Verleysen, Nonlinear Dimensionality Reduction. Springer; 2007.

[7] Y. Ma, S. Soatto, J. Kosecka, S. Sastry, An Invitation to 3-D Vision: From Images to Geometric Models. Springer; 2004.

[8] M. Tso, Reduced-rank regression and canonical analysis, Journal of the Royal Statistical Society, Series B (Methodological) 1981;43(2):183–189.

[9] H. Zhang, S. You, Z. Lin, C. Xu, Fast compressive phase retrieval under bounded noise, In: AAAI Conference on Artificial Intelligence. 2017:2884–2890.

---

¹  Netflix is a movie-renting company, which owns a lot of users' ratings on movies. The user/movie rating matrix is very sparse. The Netflix company offered one million US dollars to encourage improving the prediction on the user ratings on movies by 10%. See https://en.wikipedia.org/wiki/Netflix_Prize.

Chapter 2

Linear Models

Abstract

This chapter reviews the representative