Minimum n-rank approximation via iterative hard thresholding

DOI10.1016/J.AMC.2015.01.099zbMATH Open1338.15053arXiv1311.4291OpenAlexW2044074821MaRDI QIDQ299732FDOQ299732

Authors: Min Zhang, Lei Yang, Zhenghai Huang 

Publication date: 22 June 2016

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: The problem of recovering a low $n$-rank tensor is an extension of sparse recovery problem from the low dimensional space (matrix space) to the high dimensional space (tensor space) and has many applications in computer vision and graphics such as image inpainting and video inpainting. In this paper, we consider a new tensor recovery model, named as minimum $n$-rank approximation (MnRA), and propose an appropriate iterative hard thresholding algorithm with giving the upper bound of the $n$-rank in advance. The convergence analysis of the proposed algorithm is also presented. Particularly, we show that for the noiseless case, the linear convergence with rate $frac12$ can be obtained for the proposed algorithm under proper conditions. Additionally, combining an effective heuristic for determining $n$-rank, we can also apply the proposed algorithm to solve MnRA when $n$-rank is unknown in advance. Some preliminary numerical results on randomly generated and real low $n$-rank tensor completion problems are reported, which show the efficiency of the proposed algorithms.

Full work available at URL: https://arxiv.org/abs/1311.4291

Recommendations

• Iterative \(p\)-shrinkage thresholding algorithm for low Tucker rank tensor recovery
• An inexact continuation accelerated proximal gradient algorithm for low \textit{n}-rank tensor recovery
• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• Low rank tensor recovery via iterative hard thresholding
• Iterative hard thresholding for low CP-rank tensor models

zbMATH Keywords

compressed sensingiterative hard thresholdinglow-\( n\)-rank tensor recoverytensor completion

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69)

Cites Work

• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• Exact matrix completion via convex optimization
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Algorithm 862
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• Iterative hard thresholding for compressed sensing
• A reweighted nuclear norm minimization algorithm for low rank matrix recovery
• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• Matrix Completion From a Few Entries
• Fixed point and Bregman iterative methods for matrix rank minimization
• Iterative thresholding for sparse approximations
• Interior-point method for nuclear norm approximation with application to system identification
• Convex multi-task feature learning
• Matrix recipes for hard thresholding methods
• Learning with tensors: a framework based on convex optimization and spectral regularization
• Robust low-rank tensor recovery: models and algorithms
• Title not available (Why is that?)
• Tensor Completion in Hierarchical Tensor Representations
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
• A Fixed Point Iterative Method for Low $n$-Rank Tensor Pursuit
• Restricted $p$-Isometry Properties of Nonconvex Matrix Recovery
• Convergence of fixed-point continuation algorithms for matrix rank minimization
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• An iterative algorithm for third-order tensor multi-rank minimization

Cited In (6)

• Iterative hard thresholding for low CP-rank tensor models
• Continuity, differentiability and semismoothness of generalized tensor functions
• Iterative \(p\)-shrinkage thresholding algorithm for low Tucker rank tensor recovery
• Low-Rank Tensor Recovery using Sequentially Optimal Modal Projections in Iterative Hard Thresholding (SeMPIHT)
• Null space conditions and thresholds for rank minimization
• $N$-Dimensional Tensor Completion for Nuclear Magnetic Resonance Relaxometry

Uses Software

• PROPACK
• TensorToolbox
• N-way Toolbox
• ADMiRA

This page was built for publication: Minimum \( n\)-rank approximation via iterative hard thresholding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299732)