Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExact matrix completion based on low rank Hankel structure in the Fourier domain
278
0
0.0
(
0
)
Added by
Ke Wei
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Matrix completion is about recovering a matrix from its partial revealed entries, and it can often be achieved by exploiting the inherent simplicity or low dimensional structure of the target matrix. For instance, a typical notion of matrix simplicity is low rank. In this paper we study matrix completion based on another low dimensional structure, namely the low rank Hankel structure in the Fourier domain. It is shown that matrices with this structure can be exactly recovered by solving a convex optimization program provided the sampling complexity is nearly optimal. Empirical results are also presented to justify the effectiveness of the convex method.
rate research
Read More
This work considers two popular minimization problems: (i) the minimization of a general convex function $f(mathbf{X})$ with the domain being positive semi-definite matrices; (ii) the minimization of a general convex function $f(mathbf{X})$ regularized by the matrix nuclear norm $|mathbf{X}|_*$ with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable $mathbf{X} = mathbf{U}mathbf{U}^top $ (for semi-definite matrices) or $mathbf{X}=mathbf{U}mathbf{V}^top $ (for general matrices) and also replace the nuclear norm $|mathbf{X}|_*$ with $(|mathbf{U}|_F^2+|mathbf{V}|_F^2)/2$. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local search algorithms to find a global optimizer even with random initializations.
We propose a new Riemannian geometry for fixed-rank matrices that is specifically tailored to the low-rank matrix completion problem. Exploiting the degree of freedom of a quotient space, we tune the metric on our search space to the particular least square cost function. At one level, it illustrates in a novel way how to exploit the versatile framework of optimization on quotient manifold. At another level, our algorithm can be considered as an improved version of LMaFit, the state-of-the-art Gauss-Seidel algorithm. We develop necessary tools needed to perform both first-order and second-order optimization. In particular, we propose gradient descent schemes (steepest descent and conjugate gradient) and trust-region algorithms. We also show that, thanks to the simplicity of the cost function, it is numerically cheap to perform an exact linesearch given a search direction, which makes our algorithms competitive with the state-of-the-art on standard low-rank matrix completion instances.
In a typical MIMO radar scenario, transmit nodes transmit orthogonal waveforms, while each receive node performs matched filtering with the known set of transmit waveforms, and forwards the results to the fusion center. Based on the data it receives from multiple antennas, the fusion center formulates a matrix, which, in conjunction with standard array processing schemes, such as MUSIC, leads to target detection and parameter estimation. In MIMO radars with compressive sensing (MIMO-CS), the data matrix is formulated by each receive node forwarding a small number of compressively obtained samples. In this paper, it is shown that under certain conditions, in both sampling cases, the data matrix at the fusion center is low-rank, and thus can be recovered based on knowledge of a small subset of its entries via matrix completion (MC) techniques. Leveraging the low-rank property of that matrix, we propose a new MIMO radar approach, termed, MIMO-MC radar, in which each receive node either performs matched filtering with a small number of randomly selected dictionary waveforms or obtains sub-Nyquist samples of the received signal at random sampling instants, and forwards the results to a fusion center. Based on the received samples, and with knowledge of the sampling scheme, the fusion center partially fills the data matrix and subsequently applies MC techniques to estimate the full matrix. MIMO-MC radars share the advantages of the recently proposed MIMO-CS radars, i.e., high resolution with reduced amounts of data, but unlike MIMO-CS radars do not require grid discretization. The MIMO-MC radar concept is illustrated through a linear uniform array configuration, and its target estimation performance is demonstrated via simulations.
Suppose that a solution $widetilde{mathbf{x}}$ to an underdetermined linear system $mathbf{b} = mathbf{A} mathbf{x}$ is given. $widetilde{mathbf{x}}$ is approximately sparse meaning that it has a few large components compared to other small entries. However, the total number of nonzero components of $widetilde{mathbf{x}}$ is large enough to violate any condition for the uniqueness of the sparsest solution. On the other hand, if only the dominant components are considered, then it will satisfy the uniqueness conditions. One intuitively expects that $widetilde{mathbf{x}}$ should not be far from the true sparse solution $mathbf{x}_0$. We show that this intuition is the case by providing an upper bound on $| widetilde{mathbf{x}} - mathbf{x}_0|$ which is a function of the magnitudes of small components of $widetilde{mathbf{x}}$ but independent from $mathbf{x}_0$. This result is extended to the case that $mathbf{b}$ is perturbed by noise. Additionally, we generalize the upper bounds to the low-rank matrix recovery problem.
The task of reconstructing a matrix given a sample of observedentries is known as the matrix completion problem. It arises ina wide range of problems, including recommender systems, collaborativefiltering, dimensionality reduction, image processing, quantum physics or multi-class classificationto name a few. Most works have focused on recovering an unknown real-valued low-rankmatrix from randomly sub-sampling its entries.Here, we investigate the case where the observations take a finite number of values, corresponding for examples to ratings in recommender systems or labels in multi-class classification.We also consider a general sampling scheme (not necessarily uniform) over the matrix entries.The performance of a nuclear-norm penalized estimator is analyzed theoretically.More precisely, we derive bounds for the Kullback-Leibler divergence between the true and estimated distributions.In practice, we have also proposed an efficient algorithm based on lifted coordinate gradient descent in order to tacklepotentially high dimensional settings.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
