An alternating direction algorithm for matrix completion with nonnegative factors

This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M are given, and (ii) low-rank matrix completion where nonnegativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on the classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.     

A mean value algorithm for Toeplitz matrix completion

In this paper, we propose a new mean value algorithm for the Toeplitz matrix completion based on the singular value thresholding (SVT) algorithm. The completion matrices generated by the new algorithm keep a feasible Toeplitz structure. Meanwhile, we prove the convergence of the new algorithm under some reasonal conditions. Finally, we show the new algorithm is much more effective than the ALM (augmented Lagrange multiplier) algorithm through numerical experiments and image inpainting.     

On the matrix completion problem for multivariate filter bank construction

We survey the main techniques for the construction of multivariate filter banks and present new results about special matrices of order four and eight suitable for their construction. Qiuhui Chen: Supported in part by NSFC under grant 10201034 and project-sponsored by SRF for ROCS, SEM. Charles A. Micchelli: Supported in part by the US National Science Foundation under grant CCR-0407476. Yuesheng Xu: All correspondence to this author. Supported in part by the US National Science Foundation under grant CCR-0407476, by the Natural Science Foundation of China under grant 10371122 and by the Chinese Academy of Sciences under the program “One Hundred Distinguished Chinese Young Scientists”.     

Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion

A spectrally sparse signal of order r is a mixture of r damped or undamped complex sinusoids. This paper investigates the problem of reconstructing spectrally sparse signals from a random subset of n regular time domain samples, which can be reformulated as a low rank Hankel matrix completion problem. We introduce an iterative hard thresholding (IHT) algorithm and a fast iterative hard thresholding (FIHT) algorithm for efficient reconstruction of spectrally sparse signals via low rank Hankel matrix completion. Theoretical recovery guarantees have been established for FIHT, showing that $O(r^2{\log }^2?(n))$ number of samples are sufficient for exact recovery with high probability. Empirical performance comparisons establish significant computational advantages for IHT and FIHT. In particular, numerical simulations on 3D arrays demonstrate the capability of FIHT on handling large and high-dimensional real data.     

Robust linear optimization under matrix completion

Linear programming models have been widely used in input-output analysis for analyzing the interdependence of industries in economics and in environmental science.In these applications,some of the entries of the coefficient matrix cannot be measured physically or there exists sampling errors.However,the coefficient matrix can often be low-rank.We characterize the robust counterpart of these types of linear programming problems with uncertainty set described by the nuclear norm.Simulations for the input-output analysis show that the new paradigm can be helpful.     

Local search algorithms for finding the Hamiltonian completion number of line graphs

Given a graph G=(V,E), the Hamiltonian completion number of G, HCN(G), is the minimum number of edges to be added to G to make it Hamiltonian. This problem is known to be -hard even when G is a line graph. In this paper, local search algorithms for finding HCN(G) when G is a line graph are proposed. The adopted approach is mainly based on finding a set of edge-disjoint trails that dominates all the edges of the root graph of G. Extensive computational experiments conducted on a wide set of instances allow to point out the behavior of the proposed algorithms with respect to both the quality of the solutions and the computation time.     

On the interval completion of chordal graphs

For a given graph G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F) of G is an interval graph and |F| is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.     

Sparse quasi-Newton updates with positive definite matrix completion

Quasi-Newton methods are powerful techniques for solving unconstrained minimization problems. Variable metric methods, which include the BFGS and DFP methods, generate dense positive definite approximations and, therefore, are not applicable to large-scale problems. To overcome this difficulty, a sparse quasi-Newton update with positive definite matrix completion that exploits the sparsity pattern of the Hessian is proposed. The proposed method first calculates a partial approximate Hessian , where , using an existing quasi-Newton update formula such as the BFGS or DFP methods. Next, a full matrix H _k+1, which is a maximum-determinant positive definite matrix completion of , is obtained. If the sparsity pattern E (or its extension F) has a property related to a chordal graph, then the matrix H _k+1 can be expressed as products of some sparse matrices. The time and space requirements of the proposed method are lower than those of the BFGS or the DFP methods. In particular, when the Hessian matrix is tridiagonal, the complexities become O(n). The proposed method is shown to have superlinear convergence under the usual assumptions.      

Projected Landweber iteration for matrix completion

Recovering an unknown low-rank or approximately low-rank matrix from a sampling set of its entries is known as the matrix completion problem. In this paper, a nonlinear constrained quadratic program problem concerning the matrix completion is obtained. A new algorithm named the projected Landweber iteration (PLW) is proposed, and the convergence is proved strictly. Numerical results show that the proposed algorithm can be fast and efficient under suitable prior conditions of the unknown low-rank matrix.     

A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm

In this paper, we give a lower bound guaranteeing exact matrix completion via singular value thresholding (SVT) algorithm. The analysis shows that when the parameter in SVT algorithm is beyond some finite scalar, one can recover some unknown low-rank matrices exactly with high probability by solving a strictly convex optimization problem. Furthermore, we give an explicit expression for such a finite scalar. This result in the paper not only has theoretical interests, but also guides us to choose suitable parameters in the SVT algorithm.     

Parallel stochastic gradient algorithms for large-scale matrix completion

This paper develops Jellyfish, an algorithm for solving data-processing problems with matrix-valued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and least-squares problems regularized by the nuclear norm or $\gamma _2$ -norm. Jellyfish implements a projected incremental gradient method with a biased, random ordering of the increments. This biased ordering allows for a parallel implementation that admits a speed-up nearly proportional to the number of processors. On large-scale matrix completion tasks, Jellyfish is orders of magnitude more efficient than existing codes. For example, on the Netflix Prize data set, prior art computes rating predictions in approximately 4 h, while Jellyfish solves the same problem in under 3 min on a 12 core workstation.     

Twisted factorization of a banded matrix

The twisted factorization of a tridiagonal matrix T plays an important role in inverse iteration as featured in the MRRR algorithm. The twisted structure simplifies the computation of the eigenvector approximation and can also improve the accuracy. A tridiagonal twisted factorization is given by T=M _k Δ _k N _k where Δ _k is diagonal, M _k ,N _k have unit diagonals, and the k-th column of M _k and the k-th row of N _k correspond to the k-th column and row of the identity, that is . This paper gives a constructive proof for the existence of the twisted factorizations of a general banded matrix A. We show that for a given twist index k, there actually are two such factorizations. We also investigate the implications on inverse iteration and discuss the role of pivoting.      

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.     

Controllability completion problems of partial upper triangular matrices

The main result of this paper states sufficient conditions for the existence of a completion A_c of an n × n partial upper triangular matrix A, such that the pair (A_cB) has prescribed controllability indices, being B an n×m matrix. If A is a partial Hessenberg matrix some conditions may be dropped. An algorithm that obtains a completion A_c of A such that pair (A_ce_k) is completely controllable, where e_k is a unit vector, is used to proof the results.     

A very fast algorithm for matrix factorization

We present a very fast algorithm for general matrix factorization of a data matrix for use in the statistical analysis of high-dimensional data via latent factors. Such data are prevalent across many application areas and generate an ever-increasing demand for methods of dimension reduction in order to undertake the statistical analysis of interest. Our algorithm uses a gradient-based approach which can be used with an arbitrary loss function provided the latter is differentiable. The speed and effectiveness of our algorithm for dimension reduction is demonstrated in the context of supervised classification of some real high-dimensional data sets from the bioinformatics literature.     

Superfast algorithms for Cauchy-like matrix computations and extensions

An effective algorithm of [M. Morf, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, CA, 1974; in: Proceedings of the IEEE International Conference on ASSP, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 954–959; R.R. Bitmead and B.D.O. Anderson, Linear Algebra Appl. 34 (1980) 103–116] computes the solution to a strongly nonsingular Toeplitz or Toeplitz-like linear system , a short displacement generator for the inverse T⁻¹ of T, and det T. We extend this algorithm to the similar computations with n×n Cauchy and Cauchy-like matrices. Recursive triangular factorization of such a matrix can be computed by our algorithm at the cost of executing O(nr²log³ n) arithmetic operations, where r is the scaling rank of the input Cauchy-like matrix C (r=1 if C is a Cauchy matrix). Consequently, the same cost bound applies to the computation of the determinant of C, a short scaling generator of C⁻¹, and the solution to a nonsingular linear system of n equations with such a matrix C. (Our algorithm does not use the reduction to Toeplitz-like computations.) We also relax the assumptions of strong nonsingularity and even nonsingularity of the input not only for the computations in the field of complex or real numbers, but even, where the algorithm runs in an arbitrary field. We achieve this by using randomization, and we also show a certain improvement of the respective algorithm by Kaltofen for Toeplitz-like computations in an arbitrary field. Our subject has close correlation to rational tangential (matrix) interpolation under passivity condition (e.g., to Nevanlinna–Pick tangential interpolation problems) and has further impact on the decoding of algebraic codes.