ROBUST INEXACT ALTERNATING OPTIMIZATION FOR MATRIX COMPLETION WITH OUTLIERS

We investigate the problem of robust matrix completion with a fraction of observation corrupted by sparsity outlier noise. We propose an algorithmic framework based on the ADMM algorithm for a non-convex optimization, whose objective function consists of an $\ell_1$ norm data fidelity and a rank constraint. To reduce the computational cost per iteration, two inexact schemes are developed to replace the most time-consuming step in the generic ADMM algorithm. The resulting algorithms remarkably outperform the existing solvers for robust matrix completion with outlier noise. When the noise is severe and the underlying matrix is ill-conditioned, the proposed algorithms are faster and give more accurate solutions than state-of-the-art robust matrix completion approaches.     

A nonconvex approach to low‐rank matrix completion using convex optimization

This paper deals with the problem of recovering an unknown low‐rank matrix from a sampling of its entries. For its solution, we consider a nonconvex approach based on the minimization of a nonconvex functional that is the sum of a convex fidelity term and a nonconvex, nonsmooth relaxation of the rank function. We show that by a suitable choice of this nonconvex penalty, it is possible, under mild assumptions, to use also in this matrix setting the iterative forward–backward splitting method. Specifically, we propose the use of certain parameter dependent nonconvex penalties that with a good choice of the parameter value allow us to solve in the backward step a convex minimization problem, and we exploit this result to prove the convergence of the iterative forward–backward splitting algorithm. Based on the theoretical results, we develop for the solution of the matrix completion problem the efficient iterative improved matrix completion forward–backward algorithm, which exhibits lower computing times and improved recovery performance when compared with the best state‐of‐the‐art algorithms for matrix completion. Copyright © 2016 John Wiley & Sons, Ltd.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.     

Low Tucker rank tensor completion using a symmetric block coordinate descent method

Low Tucker rank tensor completion has wide applications in science and engineering. Many existing approaches dealt with the Tucker rank by unfolding matrix rank. However, unfolding a tensor to a matrix would destroy the data's original multi-way structure, resulting in vital information loss and degraded performance. In this article, we establish a relationship between the Tucker ranks and the ranks of the factor matrices in Tucker decomposition. Then, we reformulate the low Tucker rank tensor completion problem as a multilinear low rank matrix completion problem. For the reformulated problem, a symmetric block coordinate descent method is customized. For each matrix rank minimization subproblem, the classical truncated nuclear norm minimization is adopted. Furthermore, temporal characteristics in image and video data are introduced to such a model, which benefits the performance of the method. Numerical simulations illustrate the efficiency of our proposed models and methods.     

Exact Matrix Completion via Convex Optimization

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys $m\ge C\,n^{1.2}r\log n$ for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.     

Robust tensor completion using transformed tensor singular value decomposition

In this article, we study robust tensor completion by using transformed tensor singular value decomposition (SVD), which employs unitary transform matrices instead of discrete Fourier transform matrix that is used in the traditional tensor SVD. The main motivation is that a lower tubal rank tensor can be obtained by using other unitary transform matrices than that by using discrete Fourier transform matrix. This would be more effective for robust tensor completion. Experimental results for hyperspectral, video and face datasets have shown that the recovery performance for the robust tensor completion problem by using transformed tensor SVD is better in peak signal‐to‐noise ratio than that by using Fourier transform and other robust tensor completion methods.     

Robust PCA and subspace tracking from incomplete observations using \ell _0-surrogates

Many applications in data analysis rely on the decomposition of a data matrix into a low-rank and a sparse component. Existing methods that tackle this task use the nuclear norm and \(\ell _1\) -cost functions as convex relaxations of the rank constraint and the sparsity measure, respectively, or employ thresholding techniques. We propose a method that allows for reconstructing and tracking a subspace of upper-bounded dimension from incomplete and corrupted observations. It does not require any a priori information about the number of outliers. The core of our algorithm is an intrinsic Conjugate Gradient method on the set of orthogonal projection matrices, the so-called Grassmannian. Non-convex sparsity measures are used for outlier detection, which leads to improved performance in terms of robustly recovering and tracking the low-rank matrix. In particular, our approach can cope with more outliers and with an underlying matrix of higher rank than other state-of-the-art methods.     

A non-convex tensor rank approximation for tensor completion

Low-rankness has been widely exploited for the tensor completion problem. Recent advances have suggested that the tensor nuclear norm often leads to a promising approximation for the tensor rank. It treats the singular values equally to pursue the convexity of the objective function, while the singular values for the practical images have clear physical meanings with different importance and should be treated differently. In this paper, we propose a non-convex logDet function as a smooth approximation for tensor rank instead of the convex tensor nuclear norm and introduce it into the low-rank tensor completion problem. An alternating direction method of multiplier (ADMM)-based method is developed to solve the problem. Experimental results have shown that the proposed method can significantly outperform existing state-of-the-art nuclear norm-based methods for tensor completion.     

Efficient algorithms for robust and stable principal component pursuit problems

The problem of recovering a low-rank matrix from a set of observations corrupted with gross sparse error is known as the robust principal component analysis (RPCA) and has many applications in computer vision, image processing and web data ranking. It has been shown that under certain conditions, the solution to the NP-hard RPCA problem can be obtained by solving a convex optimization problem, namely the robust principal component pursuit (RPCP). Moreover, if the observed data matrix has also been corrupted by a dense noise matrix in addition to gross sparse error, then the stable principal component pursuit (SPCP) problem is solved to recover the low-rank matrix. In this paper, we develop efficient algorithms with provable iteration complexity bounds for solving RPCP and SPCP. Numerical results on problems with millions of variables and constraints such as foreground extraction from surveillance video, shadow and specularity removal from face images and video denoising from heavily corrupted data show that our algorithms are competitive to current state-of-the-art solvers for RPCP and SPCP in terms of accuracy and speed.     

An implementable proximal point algorithmic framework for nuclear norm minimization

The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature.     

Lanczos method for large-scale quaternion singular value decomposition

In many color image processing and recognition applications, one of the most important targets is to compute the optimal low-rank approximations to color images, which can be reconstructed with a small number of dominant singular value decomposition (SVD) triplets of quaternion matrices. All existing methods are designed to compute all SVD triplets of quaternion matrices at first and then to select the necessary dominant ones for reconstruction. This way costs quite a lot of operational flops and CPU times to compute many superfluous SVD triplets. In this paper, we propose a Lanczos-based method of computing partial (several dominant) SVD triplets of the large-scale quaternion matrices. The partial bidiagonalization of large-scale quaternion matrices is derived by using the Lanczos iteration, and the reorthogonalization and thick-restart techniques are also utilized in the implementation. An algorithm is presented to compute the partial quaternion singular value decomposition. Numerical examples, including principal component analysis, color face recognition, video compression and color image completion, illustrate that the performance of the developed Lanczos-based method for low-rank quaternion approximation is better than that of the state-of-the-art methods.

     

Deterministic algorithms for matrix completion

The goal of the matrix completion problem is to retrieve an unknown real matrix from a small subset of its entries. This problem comes up in many application areas, and has received a great deal of attention in the context of the Netflix challenge. This setup usually represents our partial knowledge of some information domain. Unknown entries may be due to the unavailability of some relevant experimental data. One approach to this problem starts by selecting a complexity measure of matrices, such as rank or trace norm. The corresponding algorithm outputs a matrix of lowest possible complexity that agrees with the partially specified matrix. The performance of the above algorithm under the assumption that the revealed entries are sampled randomly has received considerable attention (e.g., Refs. Srebro et al., 2005; COLT, 2005; Foygel and Srebro, 2011; Candes and Tao, 2010; Recht, 2009; Keshavan et al., 2010; Koltchinskii et al., 2010). Here we ask what can be said if the observed entries are chosen deterministically. We prove generalization error bounds for such deterministic algorithms, that resemble the results of Refs. Srebro et al. (2005); COLT (2005); Foygel and Srebro (2011) for the randomized algorithms. We still do not understand which sets of entries in a given matrix can be used to properly reconstruct it. Our hope is that the present work sheds some light on this problem. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 306–317, 2014     

Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions

In this paper, we improve existing results in the field of compressed sensing and matrix completion when sampled data may be grossly corrupted. We introduce three new theorems. (1) In compressed sensing, we show that if the m×n sensing matrix has independent Gaussian entries, then one can recover a sparse signal x exactly by tractable ? ₁ minimization even if a positive fraction of the measurements are arbitrarily corrupted, provided the number of nonzero entries in x is O(m/(log(n/m)+1)). (2) In the very general sensing model introduced in Candès and Plan (IEEE Trans. Inf. Theory 57(11):7235–7254, 2011) and assuming a positive fraction of corrupted measurements, exact recovery still holds if the signal now has O(m/(log² n)) nonzero entries. (3) Finally, we prove that one can recover an n×n low-rank matrix from m corrupted sampled entries by tractable optimization provided the rank is on the order of O(m/(nlog² n)); again, this holds when there is a positive fraction of corrupted samples.     

Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization

The matrix rank minimization problem has applications in many fields, such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem (Math. Program., doi:, 2009). By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.     

Confluent Vandermonde matrices,divided differences,and Lagrange–Hermite interpolation over quaternions

We introduce the notion of a confluent Vandermonde matrix with quaternion entries and discuss its connection with Lagrange–Hermite interpolation over quaternions. The formula for the rank of a confluent Vandermonde matrix is obtained as well as the representation formula for divided differences of quaternion polynomials. Extensions of these results to the power series setting include the formula for the rank of a confluent Cauchy matrix and norm-constrained Lagrange–Hermite interpolation by square summable power series over quaternions.     

Spectral Algorithms for Tensor Completion

In the tensor completion problem, one seeks to estimate a low‐rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial‐time algorithms. Among the latter, the best statistical guarantees have been proved, for third‐order tensors, using the sixth level of the sum‐of‐squares (sos ) semidefinite programming hierarchy. However, the sos approach does not scale well to large problem instances. By contrast, spectral methods—based on unfolding or matricizing the tensor—are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new method, based on unfolding, which outperforms naive ones for symmetric k^th‐order tensors of rank r. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third‐order tensors, our algorithm matches the sos method in terms of sample size (requiring about rd^3/2 revealed entries), subject to a worse rank condition (r ≪ d^3/4 rather than r ≪ d^3/2). We complement this result with a different spectral algorithm for third‐order tensors in the overcomplete (r ≥ d) regime. Under a random model, this second approach succeeds in estimating tensors of rank d ≤ r ≪ d^3/2 from about rd^3/2 revealed entries. © 2018 Wiley Periodicals, Inc.     

A solution to anisotropic suboptimal filtering problem by convex optimization

This paper considers a robust filtering problem for a linear discrete time invariant system with measured and estimated outputs. The system is exposed to random disturbances with imprecisely known distributions generated by an unknown stable shaping filter from the Gaussian white noise. The stochastic uncertainty of the input disturbance is measured by the mean anisotropy functional. The estimation error is quantified by the anisotropic norm which is a stochastic analogue of the H _∞ norm. A sufficient condition for an estimator to exist and ensure that the error is less than a given threshold value is derived in form of a convex inequality on the determinant of a positive definite matrix and two linear matrix inequalities. The suboptimal problem setting results to a set of the estimators ensuring the anisotropic norm of the error to be strictly bounded thereby providing some additional degree of freedom to impose some additional constraints on the estimator performance specification.     

A primal‐dual method for the Meyer model of cartoon and texture decomposition

In this paper, we study the original Meyer model of cartoon and texture decomposition in image processing. The model, which is a minimization problem, contains an l₁‐based TV‐norm and an l_∞‐based G‐norm. The main idea of this paper is to use the dual formulation to represent both TV‐norm and G‐norm. The resulting minimization problem of the Meyer model can be given as a minimax problem. A first‐order primal‐dual algorithm can be developed to compute the saddle point of the minimax problem. The convergence of the proposed algorithm is theoretically shown. Numerical results are presented to show that the original Meyer model can decompose better cartoon and texture components than the other testing methods.     

Convexity of the upper complex plane part of the numerical range of a quaternionic matrix

The quaternionic numerical range of a matrix with quaternion entries has a convex intersection with the upper half complex plane. The quaternionic analog of the elliptical range theorem is proved.     

The generalized centro‐symmetric and least squares generalized centro‐symmetric solutions of the matrix equation AYB + CYTD = E

An n×n real matrix P is said to be a symmetric orthogonal matrix if P = P^?1 = P^T. An n × n real matrix Y is called a generalized centro‐symmetric with respect to P, if Y = PYP. It is obvious that every matrix is also a generalized centro‐symmetric matrix with respect to I. In this work by extending the conjugate gradient approach, two iterative methods are proposed for solving the linear matrix equation and the minimum Frobenius norm residual problem over the generalized centro‐symmetric Y, respectively. By the first (second) algorithm for any initial generalized centro‐symmetric matrix, a generalized centro‐symmetric solution (least squares generalized centro‐symmetric solution) can be obtained within a finite number of iterations in the absence of round‐off errors, and the least Frobenius norm generalized centro‐symmetric solution (the minimal Frobenius norm least squares generalized centro‐symmetric solution) can be derived by choosing a special kind of initial generalized centro‐symmetric matrices. We also obtain the optimal approximation generalized centro‐symmetric solution to a given generalized centro‐symmetric matrix Y₀ in the solution set of the matrix equation (minimum Frobenius norm residual problem). Finally, some numerical examples are presented to support the theoretical results of this paper. Copyright © 2011 John Wiley & Sons, Ltd.