Any pointer for analyzing this matrix?

[divB]

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:

$$\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]$$

where $*$ denotes point-wise multiplication.

$$\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]$$

$$\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]$$

Thanks,
divB

 

[Stephen Tashi]

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?

If you choose $L \ne K\cdot M$, I'm curious how you define the "condition number" of the resulting non-square matrix.

 

[divB]

Hi Stephen,

Thanks. I have no formal requirement for this. The system should be solved via LS and stability and accuracy increases as the condition number decreases. Which definition is exactly used is not so relevant to me; the ratio between largest and smallest singular value works pretty well (cond in MATLAB) and of course works for any, non-square matrix.

divB

 

[Stephen Tashi]

I don't know if this article (PDF) is relevant, but the title "How to find a good submatrix" sounds apt.

http://www.google.com/url?sa=t&rct=...bFBqpk6Vk918dww&bvm=bv.51156542,d.aWc&cad=rja