Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Any pointer for analyzing this matrix?

  1. Aug 20, 2013 #1
    Row subset of matrix with lowest condition number


    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).

    \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 [itex]*[/itex] 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

    \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}

    Last edited: Aug 20, 2013
  2. jcsd
  3. Aug 22, 2013 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    If you choose [itex] L \ne K\cdot M [/itex], I'm curious how you define the "condition number" of the resulting non-square matrix.
  4. Aug 22, 2013 #3
    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.

  5. Aug 25, 2013 #4

    Stephen Tashi

    User Avatar
    Science Advisor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook