Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Fast and Adaptive SVD-free Algorithm for General Weighted Low-rank Recovery
67
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper is devoted to proposing a general weighted low-rank recovery model and designs a fast SVD-free computational scheme to solve it. First, our generic weighted low-rank recovery model unifies several existing approaches in the literature.~Moreover, our model readily extends to the non-convex setting. Algorithm-wise, most first-order proximal algorithms in the literature for low-rank recoveries require computing singular value decomposition (SVD). As SVD does not scale properly with the dimension of the matrices, these algorithms becomes slower when the problem size becomes larger. By incorporating the variational formulation of the nuclear norm into the sub-problem of proximal gradient descent, we avoid to compute SVD which results in significant speed-up. Moreover, our algorithm preserves the {em rank identification property} of nuclear norm [33] which further allows us to design a rank continuation scheme that asymptotically achieves the minimal iteration complexity. Numerical experiments on both toy example and real-world problems including structure from motion (SfM) and photometric stereo, background estimation and matrix completion, demonstrate the superiority of our proposed algorithm.
rate research
Read More
The problem of recovering a low-rank matrix from the linear constraints, known as affine matrix rank minimization problem, has been attracting extensive attention in recent years. In general, affine matrix rank minimization problem is a NP-hard. In our latest work, a non-convex fraction function is studied to approximate the rank function in affine matrix rank minimization problem and translate the NP-hard affine matrix rank minimization problem into a transformed affine matrix rank minimization problem. A scheme of iterative singular value thresholding algorithm is generated to solve the regularized transformed affine matrix rank minimization problem. However, one of the drawbacks for our iterative singular value thresholding algorithm is that the parameter $a$, which influences the behaviour of non-convex fraction function in the regularized transformed affine matrix rank minimization problem, needs to be determined manually in every simulation. In fact, how to determine the optimal parameter $a$ is not an easy problem. Here instead, in this paper, we will generate an adaptive iterative singular value thresholding algorithm to solve the regularized transformed affine matrix rank minimization problem. When doing so, our new algorithm will be intelligent both for the choice of the regularized parameter $lambda$ and the parameter $a$.
Fourier domain structured low-rank matrix priors are emerging as powerful alternatives to traditional image recovery methods such as total variation and wavelet regularization. These priors specify that a convolutional structured matrix, i.e., Toeplitz, Hankel, or their multi-level generalizations, built from Fourier data of the image should be low-rank. The main challenge in applying these schemes to large-scale problems is the computational complexity and memory demand resulting from lifting the image data to a large scale matrix. We introduce a fast and memory efficient approach called the Generic Iterative Reweighted Annihilation Filter (GIRAF) algorithm that exploits the convolutional structure of the lifted matrix to work in the original un-lifted domain, thus considerably reducing the complexity. Our experiments on the recovery of images from undersampled Fourier measurements show that the resulting algorithm is considerably faster than previously proposed algorithms, and can accommodate much larger problem sizes than previously studied.
Low rank matrix recovery problems, including matrix completion and matrix sensing, appear in a broad range of applications. In this work we present GNMR -- an extremely simple iterative algorithm for low rank matrix recovery, based on a Gauss-Newton linearization. On the theoretical front, we derive recovery guarantees for GNMR in both the matrix sensing and matrix completion settings. A key property of GNMR is that it implicitly keeps the factor matrices approximately balanced throughout its iterations. On the empirical front, we show that for matrix completion with uniform sampling, GNMR performs better than several popular methods, especially when given very few observations close to the information limit.
The low-rank matrix completion problem can be solved by Riemannian optimization on a fixed-rank manifold. However, a drawback of the known approaches is that the rank parameter has to be fixed a priori. In this paper, we consider the optimization problem on the set of bounded-rank matrices. We propose a Riemannian rank-adaptive method, which consists of fixed-rank optimization, rank increase step and rank reduction step. We explore its performance applied to the low-rank matrix completion problem. Numerical experiments on synthetic and real-world datasets illustrate that the proposed rank-adaptive method compares favorably with state-of-the-art algorithms. In addition, it shows that one can incorporate each aspect of this rank-adaptive framework separately into existing algorithms for the purpose of improving performance.
Low rank matrix recovery is the focus of many applications, but it is a NP-hard problem. A popular way to deal with this problem is to solve its convex relaxation, the nuclear norm regularized minimization problem (NRM), which includes LASSO as a special case. There are some regularization parameter selection results for LASSO in vector case, such as screening rules, which improve the efficiency of the algorithms. However, there are no corresponding parameter selection results for NRM in matrix case. In this paper, we build up a novel rule to choose the regularization parameter for NRM under the help of duality theory. This rule claims that the regularization parameter can be easily chosen by feasible points of NRM and its dual problem, when the rank of the desired solution is no more than a given constant. In particular, we apply this idea to NRM with least square and Huber functions, and establish the easily calculated formula of regularization parameters. Finally, we report numerical results on some signal shapes, which state that our proposed rule shrinks the interval of the regularization parameter efficiently.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
