3
$\begingroup$

I have a linear system to solve, set up as:

$\bf{Ax}=\bf{b}$

with a non-squared matrix A,

$ \bf{A}= \begin{bmatrix} 1 & A_{1} & A_{1}^2 & \cdots & A_{1}^n \\ 1 & A_{2} & A_{2}^2 & \cdots & A_{2}^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & A_{m} & A_{m}^2 & \cdots & A_{m}^n \end{bmatrix} $,

where $m$ and $n$ satisfy $m<n$, and

$A_{j} = \exp((i-1)a_j) $.

This $a_j$ satisfy $a_j >0$, and $i$ is an imaginary unit. This matrix is not a pure Vandermonde matrix because it’s not a square matrix, but it has similar formula.

I applied SVD and Tikhonov regularization to solve this system, but its solution is far from the true value. What method can I use to solve this? Is there any analytical solution for this system?

Thanks.

$\endgroup$
2
  • $\begingroup$ you have fewer equations than unknown, so $x$ is not uniquely determined --- what do you mean by "solve" ? $\endgroup$ May 27, 2017 at 21:00
  • 1
    $\begingroup$ The condition number of these matrices is usually spectacularly bad. if $m < n$ then you must apply additional constraints to get a unique solution. A lot of times people search for the solution that has the smallest 1 norm ($L_1$ optmization). My favorite is the Fast Linearized Bregman Iteration found at math.ucla.edu/applied/cam . You will need to modify the shrinkage operator to handle the complex case (shrink into the unit circle) $\endgroup$ Nov 8, 2017 at 1:58

2 Answers 2

2
$\begingroup$

Read the ancient paper entitled "Inverse of the Vandermonde Matrix with Applicataions", by L. Richard Turner, and be enlightened.

$\endgroup$
1
$\begingroup$

Vandermonde matrices are famously unstable to solve numerically. Here's some of the latest research on inverting Vandermonde matrixes: https://arxiv.org/abs/1909.08155 -- Mahdi S. Hosseini and Alfred Chen and Konstantinos N. Plataniotis (2019) "On the Closed Form Expression of Elementary Symmetric Polynomials and the Inverse of Vandermonde Matrix" -- it's about square matrices, but it will at least give you a stable algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.