# Any pointer for analyzing this matrix?

1. Aug 20, 2013

### 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} \mathrm{DFT}(x_n^{k-1})^T & \cdots & \mathrm{DFT}(x_n^{k-1})^T \end{matrix}}_{M-\mathrm{times}}\right]$$

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

Thanks,
divB

Last edited: Aug 20, 2013
2. Aug 22, 2013

### Stephen Tashi

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

3. Aug 22, 2013

### 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

4. Aug 25, 2013