On the condition number of Vandermonde matrices with pairs of nearly-colliding nodes
- PDF / 888,743 Bytes
- 24 Pages / 439.642 x 666.49 pts Page_size
- 20 Downloads / 168 Views
On the condition number of Vandermonde matrices with pairs of nearly-colliding nodes Stefan Kunis1 · Dominik Nagel1 Received: 28 October 2019 / Accepted: 24 June 2020 / © The Author(s) 2020
Abstract We prove upper and lower bounds for the spectral condition number of rectangular Vandermonde matrices with nodes on the complex unit circle. The nodes are “off the grid,” pairs of nodes nearly collide, and the studied condition number grows linearly with the inverse separation distance. Such growth rates are known in greater generality if all nodes collide or for groups of colliding nodes. For pairs of nodes, we provide reasonable sharp constants that are independent of the number of nodes as long as non-colliding nodes are well-separated. Keywords Vandermonde matrix · Colliding nodes · Condition number · Frequency analysis · Super resolution Mathematics Subject Classification (2010) 15A18 · 65T40 · 42A15
1 Introduction Vandermonde matrices with complex nodes appear in polynomial interpolation problems and many other fields of mathematics (see, e.g., the introduction of [2] and its references). In this paper, we are interested in rectangular Vandermonde matrices with nodes on the complex unit circle and with a large polynomial degree. These matrices generalize the classical discrete Fourier matrices to non-equispaced nodes and the involved polynomial degree is also called bandwidth. The condition number of those matrices has recently become important in the context of stability analysis Stefan Kunis
[email protected] Dominik Nagel [email protected] 1
Institute of Mathematics and Research Center of Cellular Nanoanalytics, Osnabr¨uck University, Osnabrueck, Germany
Numerical Algorithms
of super-resolution algorithms like Prony’s method [6, 15], the matrix pencil method [12, 18], the ESPRIT algorithm [20, 21], and the MUSIC algorithm [17, 22]. If the nodes of such a Vandermonde matrix are all well-separated, with minimal separation distance greater than the inverse bandwidth, bounds on the condition number are established for example in [2, 5, 14, 18]. If nodes are nearly colliding, i.e., their distance is smaller than the inverse bandwidth, the behavior of the condition number is not yet fully understood. The seminal paper [9] coined the term (inverse) super-resolution factor for the product of the bandwidth and the separation distance of the nodes. For M nodes on a grid, the results in [7, 9] imply that the condition number grows like the super-resolution factor raised to the power of M − 1 if all nodes nearly collide. More recently, the practically relevant situation of groups of nearly colliding nodes was studied in [1, 4, 16, 19]. In different setups and oversimplifying a bit, all of these refinements are able to replace the exponent M − 1 by the smaller number m − 1, where m denotes the number of nodes that are in the largest group of nearly colliding nodes. The authors of [1, 19] focus on quite specific quantities in an optimization approach and in the so-called Prony mapping, respectively. In contrast, the conditio
Data Loading...
