Behavior of the minimum singular value of a random Vandermonde matrix

Gabriel H. Tucci; Philip A. Whiting

doi:10.1109/ISIT.2012.6283953

Behavior of the minimum singular value of a random Vandermonde matrix

Gabriel H. Tucci^*, Philip A. Whiting

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

1 Citation (Scopus)

Abstract

In this work we examine the behavior of the minimum singular value of random Vandermonde matrices. In particular, we prove that the minimum singular value s ₁(N) is at most N exp(-C√N) where N is the dimension of the matrix and C is a constant. Furthermore, the value of the constant C is determined explicitly. The main result is obtained in two different ways. One approach uses techniques from stochastic processes and in particular, a construction related to the Brownian bridge. The other one is a more direct analytical approach involving combinatorics and complex analysis. As a consequence, we obtain a lower bound on the maximum absolute value of a random polynomial on the unit circle, which may be of independent mathematical interest.

Original language	English
Title of host publication	2012 IEEE international symposium on information theory proceedings, ISIT 2012
Place of Publication	Piscataway, NJ
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	2441-2445
Number of pages	5
ISBN (Electronic)	9781467325790
ISBN (Print)	9781467325806
DOIs	https://doi.org/10.1109/ISIT.2012.6283953
Publication status	Published - 2012
Externally published	Yes
Event	2012 IEEE International Symposium on Information Theory, ISIT 2012 - Cambridge, MA, United States Duration: 1 Jul 2012 → 6 Jul 2012

Other

Other	2012 IEEE International Symposium on Information Theory, ISIT 2012
Country/Territory	United States
City	Cambridge, MA
Period	1/07/12 → 6/07/12

Access to Document

10.1109/ISIT.2012.6283953

Cite this

@inproceedings{9958b81445504656ac6afe4bf164b368,

title = "Behavior of the minimum singular value of a random Vandermonde matrix",

abstract = "In this work we examine the behavior of the minimum singular value of random Vandermonde matrices. In particular, we prove that the minimum singular value s 1(N) is at most N exp(-C√N) where N is the dimension of the matrix and C is a constant. Furthermore, the value of the constant C is determined explicitly. The main result is obtained in two different ways. One approach uses techniques from stochastic processes and in particular, a construction related to the Brownian bridge. The other one is a more direct analytical approach involving combinatorics and complex analysis. As a consequence, we obtain a lower bound on the maximum absolute value of a random polynomial on the unit circle, which may be of independent mathematical interest.",

author = "Tucci, {Gabriel H.} and Whiting, {Philip A.}",

year = "2012",

doi = "10.1109/ISIT.2012.6283953",

language = "English",

isbn = "9781467325806",

pages = "2441--2445",

booktitle = "2012 IEEE international symposium on information theory proceedings, ISIT 2012",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "2012 IEEE International Symposium on Information Theory, ISIT 2012 ; Conference date: 01-07-2012 Through 06-07-2012",

}

Tucci, GH & Whiting, PA 2012, Behavior of the minimum singular value of a random Vandermonde matrix. in 2012 IEEE international symposium on information theory proceedings, ISIT 2012., 6283953, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, pp. 2441-2445, 2012 IEEE International Symposium on Information Theory, ISIT 2012, Cambridge, MA, United States, 1/07/12. https://doi.org/10.1109/ISIT.2012.6283953

Behavior of the minimum singular value of a random Vandermonde matrix. / Tucci, Gabriel H.; Whiting, Philip A.
2012 IEEE international symposium on information theory proceedings, ISIT 2012. Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE), 2012. p. 2441-2445 6283953.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Behavior of the minimum singular value of a random Vandermonde matrix

AU - Tucci, Gabriel H.

AU - Whiting, Philip A.

PY - 2012

Y1 - 2012

N2 - In this work we examine the behavior of the minimum singular value of random Vandermonde matrices. In particular, we prove that the minimum singular value s 1(N) is at most N exp(-C√N) where N is the dimension of the matrix and C is a constant. Furthermore, the value of the constant C is determined explicitly. The main result is obtained in two different ways. One approach uses techniques from stochastic processes and in particular, a construction related to the Brownian bridge. The other one is a more direct analytical approach involving combinatorics and complex analysis. As a consequence, we obtain a lower bound on the maximum absolute value of a random polynomial on the unit circle, which may be of independent mathematical interest.

AB - In this work we examine the behavior of the minimum singular value of random Vandermonde matrices. In particular, we prove that the minimum singular value s 1(N) is at most N exp(-C√N) where N is the dimension of the matrix and C is a constant. Furthermore, the value of the constant C is determined explicitly. The main result is obtained in two different ways. One approach uses techniques from stochastic processes and in particular, a construction related to the Brownian bridge. The other one is a more direct analytical approach involving combinatorics and complex analysis. As a consequence, we obtain a lower bound on the maximum absolute value of a random polynomial on the unit circle, which may be of independent mathematical interest.

UR - http://www.scopus.com/inward/record.url?scp=84867521263&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2012.6283953

DO - 10.1109/ISIT.2012.6283953

M3 - Conference proceeding contribution

AN - SCOPUS:84867521263

SN - 9781467325806

SP - 2441

EP - 2445

BT - 2012 IEEE international symposium on information theory proceedings, ISIT 2012

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

T2 - 2012 IEEE International Symposium on Information Theory, ISIT 2012

Y2 - 1 July 2012 through 6 July 2012

ER -

Behavior of the minimum singular value of a random Vandermonde matrix

Abstract

Other

Access to Document

Other files and links

Fingerprint

Cite this