- #1
divB
- 85
- 0
Row subset of matrix with lowest condition number
Hi,
I have a matrix with N rows and K\cdot M \ll N columns.
Is there a generic way to choose L rows s.t. the condition number of the matrix is minimized?
I would appreciate any pointer or any hints how I could approach the problem.
Currently I am brute forcing all possible subsets and seek for the set with the smallest condition number but this is nearly undeasible.
I do not think it helps but if it does, this is the structure of the matrix: Is is a pointwise multiplication of 2 matrices. The first summand consists of K vertical "ribbons" of size N \times M. Each consists of M equal columns where the columns are the DFT of a power of a discrete random(like) signal (I do not know if this matters ...)
The second summand consists of K equal Vandermonde matrices (to be precicse, the first M columns of the DFT matrix).
Formally:
<br /> \left[\begin{matrix} \mathbf{A}_1 & \mathbf{A}_2 & \cdots & \mathbf{A}_K \end{matrix}\right] * \left[\underbrace{\begin{matrix}\mathbf{V} & \mathbf{V} & \cdots & \mathbf{V} \end{matrix}}_{K-\mathrm{times}}\right]<br />
where * denotes point-wise multiplication.
<br /> \mathbf{A}_k = \left[\underbrace{\begin{matrix}<br /> \mathrm{DFT}(x_n^{k-1})^T & \cdots & \mathrm{DFT}(x_n^{k-1})^T<br /> \end{matrix}}_{M-\mathrm{times}}\right]<br />
<br /> \mathbf{V} = \left[\begin{matrix}<br /> 1 & 1 & 1 & \cdots & 1 \\<br /> 1 & u^1 & u^2 & \cdots & u^M \\<br /> 1 & u^2 & u^4 & \cdots & u^{2M} \\<br /> \vdots & \ddots & \ddots & \ddots & \vdots \\<br /> 1 & u^N & u^{2N} & \cdots & u^{NM}<br /> \end{matrix}\right]<br />
Thanks,
divB
Hi,
I have a matrix with N rows and K\cdot M \ll N columns.
Is there a generic way to choose L rows s.t. the condition number of the matrix is minimized?
I would appreciate any pointer or any hints how I could approach the problem.
Currently I am brute forcing all possible subsets and seek for the set with the smallest condition number but this is nearly undeasible.
I do not think it helps but if it does, this is the structure of the matrix: Is is a pointwise multiplication of 2 matrices. The first summand consists of K vertical "ribbons" of size N \times M. Each consists of M equal columns where the columns are the DFT of a power of a discrete random(like) signal (I do not know if this matters ...)
The second summand consists of K equal Vandermonde matrices (to be precicse, the first M columns of the DFT matrix).
Formally:
<br /> \left[\begin{matrix} \mathbf{A}_1 & \mathbf{A}_2 & \cdots & \mathbf{A}_K \end{matrix}\right] * \left[\underbrace{\begin{matrix}\mathbf{V} & \mathbf{V} & \cdots & \mathbf{V} \end{matrix}}_{K-\mathrm{times}}\right]<br />
where * denotes point-wise multiplication.
<br /> \mathbf{A}_k = \left[\underbrace{\begin{matrix}<br /> \mathrm{DFT}(x_n^{k-1})^T & \cdots & \mathrm{DFT}(x_n^{k-1})^T<br /> \end{matrix}}_{M-\mathrm{times}}\right]<br />
<br /> \mathbf{V} = \left[\begin{matrix}<br /> 1 & 1 & 1 & \cdots & 1 \\<br /> 1 & u^1 & u^2 & \cdots & u^M \\<br /> 1 & u^2 & u^4 & \cdots & u^{2M} \\<br /> \vdots & \ddots & \ddots & \ddots & \vdots \\<br /> 1 & u^N & u^{2N} & \cdots & u^{NM}<br /> \end{matrix}\right]<br />
Thanks,
divB
Last edited: