Researcher profile

Ivan Markovsky

Ivan Markovsky contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.NA math.OC Numerical Analysis Computation Computational Geometry Computer Vision

Trust snapshot

Quick read

Trust 17 - Baseline

4works

0followers

6topics

2close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Adjusted least squares fitting of algebraic hypersurfaces

We consider the problem of fitting a set of points in Euclidean space by an algebraic hypersurface. We assume that points on a true hypersurface, described by a polynomial equation, are corrupted by zero mean independent Gaussian noise, and we estimate the coefficients of the true polynomial equation. The adjusted least squares estimator accounts for the bias present in the ordinary least squares estimator. The adjusted least squares estimator is based on constructing a quasi-Hankel matrix, which is a bias-corrected matrix of moments. For the case of unknown noise variance, the estimator is defined as a solution of a polynomial eigenvalue problem. In this paper, we present new results on invariance properties of the adjusted least squares estimator and an improved algorithm for computing the estimator for an arbitrary set of monomials in the polynomial equation.

preprint2015arXiv

Variable projection methods for approximate (greatest) common divisor computations

We consider the problem of finding for a given $N$-tuple of polynomials (real or complex) the closest $N$-tuple that has a common divisor of degree at least $d$. Extended weighted Euclidean seminorm of the coefficients is used as a measure of closeness. Two equivalent representations of the problem are considered: (i) direct parameterization over the common divisors and quotients (image representation), and (ii) Sylvester low-rank approximation (kernel representation). We use the duality between least-squares and least-norm problems to show that (i) and (ii) are closely related to mosaic Hankel low-rank approximation. This allows us to apply to the approximate common divisor problem recent results on complexity and accuracy of computations for mosaic Hankel low-rank approximation. We develop optimization methods based on the variable projection principle both for image and kernel representation. These methods have linear complexity in the degrees of the polynomials for small and large $d$. We provide a software implementation of the developed methods, which is based on a software package for structured low-rank approximation.

preprint2014arXiv

Factorization approach to structured low-rank approximation with applications

We consider the problem of approximating an affinely structured matrix, for example a Hankel matrix, by a low-rank matrix with the same structure. This problem occurs in system identification, signal processing and computer algebra, among others. We impose the low-rank by modeling the approximation as a product of two factors with reduced dimension. The structure of the low-rank model is enforced by introducing a penalty term in the objective function. The proposed local optimization algorithm is able to solve the weighted structured low-rank approximation problem, as well as to deal with the cases of missing or fixed elements. In contrast to approaches based on kernel representations (in linear algebraic sense), the proposed algorithm is designed to address the case of small targeted rank. We compare it to existing approaches on numerical examples of system identification, approximate greatest common divisor problem, and symmetric tensor decomposition and demonstrate its consistently good performance.

preprint2013arXiv

Variable projection for affinely structured low-rank approximation in weighted 2-norms

The structured low-rank approximation problem for general affine structures, weighted 2-norms and fixed elements is considered. The variable projection principle is used to reduce the dimensionality of the optimization problem. Algorithms for evaluation of the cost function, the gradient and an approximation of the Hessian are developed. For $m \times n$ mosaic Hankel matrices the algorithms have complexity $O(m^2 n)$.