Strongly stable rank and applications to matrix completion

We perform an in-depth study of strongly stable ranks of modules over a commutative ring. Here we define the strongly stable rank of a module to be the supremum of the stable ranks of its finitely generated submodules. As an application, we give non-Noetherian generalizations of known facts about outer products and matrix completions over PIRs and Dedekind domains. We construct Noetherian and non-Noetherian domains of arbitrary strongly stable rank. We also consider strongly n-generated ideals, and we characterize the rings in which every ideal is strongly 2-generated and the domains in which every ideal is strongly 3-generated.     

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.     

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.     

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.     

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     

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 modified augmented lagrange multiplier algorithm for toeplitz matrix completion

In this paper, a modified scheme is proposed for iterative completion matrices generated by the augmented Lagrange multiplier (ALM) method based on the mean value. So that the iterative completion matrices generated by the new algorithm are of the Toeplitz structure, which decrease the computation of SVD and have better approximation to solution. Convergence is discussed. Finally, the numerical experiments and inpainted images show that the new algorithm is more effective than the accelerated proximal gradient (APG) algorithm, the singular value thresholding (SVT) algorithm and the ALM algorithm, in CPU time and accuracy.     

Low rank matrix recovery from rank one measurements

We study the recovery of Hermitian low rank matrices $X\in {\mathbb{C}}^{n\times n}$ from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form $a_j{a}_j^{?}$ for some measurement vectors $a_1,\dots ,a_m$, i.e., the measurements are given by $b_j=\mathrm{tr}(X{a}_j{a}_j^{?})$. The case where the matrix $X=x{x}^{?}$ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements $b_j=|〈x,a_j〉{|}^2$) via the PhaseLift approach, which has been introduced recently. We derive bounds for the number m of measurements that guarantee successful uniform recovery of Hermitian rank r matrices, either for the vectors $a_j$, $j=1,\dots ,m$, being chosen independently at random according to a standard Gaussian distribution, or $a_j$ being sampled independently from an (approximate) complex projective t-design with $t=4$. In the Gaussian case, we require $m\ge Crn$ measurements, while in the case of 4-designs we need $m\ge \mathit{Cr}n\log ?(n)$. Our results are uniform in the sense that one random choice of the measurement vectors $a_j$ guarantees recovery of all rank r-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate 4-designs generalizes and improves a recent bound on phase retrieval due to Gross, Krahmer and Kueng. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.     

The elliptic matrix completion problem

Completions of partial elliptic matrices are studied. Given an undirected graph G, it is shown that every partial elliptic matrix with graph G can be completed to an elliptic matrix if and only if the maximal cliques of G are pairwise disjoint. Further, given a partial elliptic matrix A with undirected graph G, it is proved that if G is chordal and each specified principal submatrix defined by a pair of intersecting maximal cliques is nonsingular, then A can be completed to an elliptic matrix. Conversely, if G is nonchordal or if the regularity condition is relaxed, it is shown that there exist partial elliptic matrices which are not completable to an elliptic matrix. In the process we obtain several results concerning chordal graphs that may be of independent interest.     

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.     

Half thresholding eigenvalue algorithm for semidefinite matrix completion

The semidefinite matrix completion(SMC) problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, SMC problem and S1/2relaxation model share a unique solution. Then we prove that the global optimal solutions of S1/2regularization model are fixed points of a symmetric matrix half thresholding operator. We give an iterative scheme for solving S1/2regularization model and state convergence analysis of the iterative sequence.Through the optimal regularization parameter setting together with truncation techniques, we develop an HTE algorithm for S1/2regularization model, and numerical experiments confirm the efficiency and robustness of the proposed algorithm.     

The rank of a completion of a dedekind domain

Let D be a Dedekind domain with quotient field K. Let C_p be the completion of the localisationD_p , of D at a nonzero prime idealp, of D. Let r_p be the rank of C_p as a D-module, ier_p , is the dimension of the K-vector space K_p , = K? _DC_p . The following results on r_p are deduced from well-known theorems: if r_p is finite for at least one prime ideal p, then D is a discrete valuation ring; and D = C_p if _p = 1. If D is a discrete valuation ring, then r_p = dimExt(K, D) + 1. A module M is extensionless if every extension of M by M splits. The D-module r_C is an estensionless indecomposable module. If r_C is infinite for every nonzero prime ideal, it is shown that an estensionless D-module of finite rank is a direct sum or certain rank one modulcs.     

A non-linear structure preserving matrix method for the low rank approximation of the Sylvester resultant matrix

A non-linear structure preserving matrix method for the computation of a structured low rank approximation of the Sylvester resultant matrix S(f,g) of two inexact polynomials f=f(y) and g=g(y) is considered in this paper. It is shown that considerably improved results are obtained when f(y) and g(y) are processed prior to the computation of , and that these preprocessing operations introduce two parameters. These parameters can either be held constant during the computation of , which leads to a linear structure preserving matrix method, or they can be incremented during the computation of , which leads to a non-linear structure preserving matrix method. It is shown that the non-linear method yields a better structured low rank approximation of S(f,g) and that the assignment of f(y) and g(y) is important because may be a good structured low rank approximation of S(f,g), but may be a poor structured low rank approximation of S(g,f) because its numerical rank is not defined. Examples that illustrate the differences between the linear and non-linear structure preserving matrix methods, and the importance of the assignment of f(y) and g(y), are shown.     

Ranking assignments in order of increasing completion time

Bottleneck Assignment Problem has already been solved by Gross [5], Gar-Finkel [3] and Bhatia [1]. Starting with an assignment yielding minimum completion time, the present paper presents two procedures for ranking various assignments in order of increasing completion time. In the first, closed circuits satisfying certain conditions are found. Non-existence of such circuits at a particular time imply no assignment yielding that completion time. In the second procedure a cost minimizing assignment problem is solved to get an assignment yielding next best time, Murty's [8] cost ranking procedure has been suitably modified for time ranking and is discussed in a note in this paper.     

A note on the equality of rank and trace for an idempotent matrix

The equality of rank and trace for an idempotent matrix is established by means of elementary matrix factorizations. The proof is substantially simpler than most found in the literature.     

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.