Tensor completion for estimating missing values in visual data
Ji yin Liu, Przemysław Musialski, Peter Wonka et al. · IEEE International Conference on Computer Vision (ICCV) · 2009
In this paper we propose an algorithm to estimate missing values in tensors of visual data. The values can be missing due to problems in the acquisition process, or because the user manually identified unwanted outliers. Our algorithm works even with a small amount of samples and it can propagate structure to fill larger missing regions. Our methodology is built on recent studies about matrix completion using the matrix trace norm. The contribution of our paper is to extend the matrix case to the tensor case by laying out the theoretical foundations and then by building a working algorithm. First, we propose a definition for the tensor trace norm, that generalizes the established definition of the matrix trace norm. Second, similar to matrix completion, the tensor completion is formulated as a convex optimization problem. Unfortunately, the straightforward problem extension is significantly harder to solve than the matrix case because of the dependency among multiple constraints. To tackle this problem, we employ a relaxation technique to separate the dependant relationships and use the block coordinate descent (BCD) method to achieve a globally optimal solution. Our experiments show potential applications of our algorithm and the quantitative evaluation indicates that our method is more accurate and robust than heuristic approaches.
Cited by 119 works. doi:10.1109/iccv.2009.5459463
Authors
References
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Shape and motion from image streams under orthography: a factorization method
- Image inpainting
- A Singular Value Thresholding Algorithm for Matrix Completion
- Exact Matrix Completion via Convex Optimization
- Missing value estimation methods for DNA microarrays
- Maximum-Margin Matrix Factorization
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Multi-Task Feature Learning