- #1
divB
- 87
- 0
Row subset of matrix with lowest condition number
Hi,
I have a matrix with [itex]N[/itex] rows and [itex]K\cdot M \ll N[/itex] columns.
Is there a generic way to choose [itex]L[/itex] 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 [itex]K[/itex] vertical "ribbons" of size [itex]N \times M[/itex]. Each consists of [itex]M[/itex] 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 [itex]K[/itex] equal Vandermonde matrices (to be precicse, the first [itex]M[/itex] columns of the DFT matrix).
Formally:
[tex]
\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]
[/tex]
where [itex]*[/itex] denotes point-wise multiplication.
[tex]
\mathbf{A}_k = \left[\underbrace{\begin{matrix}
\mathrm{DFT}(x_n^{k-1})^T & \cdots & \mathrm{DFT}(x_n^{k-1})^T
\end{matrix}}_{M-\mathrm{times}}\right]
[/tex]
[tex]
\mathbf{V} = \left[\begin{matrix}
1 & 1 & 1 & \cdots & 1 \\
1 & u^1 & u^2 & \cdots & u^M \\
1 & u^2 & u^4 & \cdots & u^{2M} \\
\vdots & \ddots & \ddots & \ddots & \vdots \\
1 & u^N & u^{2N} & \cdots & u^{NM}
\end{matrix}\right]
[/tex]
Thanks,
divB
Hi,
I have a matrix with [itex]N[/itex] rows and [itex]K\cdot M \ll N[/itex] columns.
Is there a generic way to choose [itex]L[/itex] 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 [itex]K[/itex] vertical "ribbons" of size [itex]N \times M[/itex]. Each consists of [itex]M[/itex] 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 [itex]K[/itex] equal Vandermonde matrices (to be precicse, the first [itex]M[/itex] columns of the DFT matrix).
Formally:
[tex]
\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]
[/tex]
where [itex]*[/itex] denotes point-wise multiplication.
[tex]
\mathbf{A}_k = \left[\underbrace{\begin{matrix}
\mathrm{DFT}(x_n^{k-1})^T & \cdots & \mathrm{DFT}(x_n^{k-1})^T
\end{matrix}}_{M-\mathrm{times}}\right]
[/tex]
[tex]
\mathbf{V} = \left[\begin{matrix}
1 & 1 & 1 & \cdots & 1 \\
1 & u^1 & u^2 & \cdots & u^M \\
1 & u^2 & u^4 & \cdots & u^{2M} \\
\vdots & \ddots & \ddots & \ddots & \vdots \\
1 & u^N & u^{2N} & \cdots & u^{NM}
\end{matrix}\right]
[/tex]
Thanks,
divB
Last edited: