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

 

[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

 

[blue_raver22]

Hi divB,

Thank you for your question. Analyzing a matrix with a large number of rows and a low condition number can be a challenging task. However, there are a few pointers that can help guide your analysis:

1. Understand the concept of condition number: The condition number of a matrix is a measure of how sensitive its output is to changes in its input. A lower condition number indicates that the matrix is less sensitive to changes, making it more stable and easier to analyze.

2. Use specialized algorithms: There are specialized algorithms available for computing the condition number of a matrix. These algorithms take advantage of the structure of the matrix to efficiently calculate its condition number. One such algorithm is the QR decomposition method, which decomposes a matrix into an orthogonal matrix and an upper triangular matrix and can be used to calculate the condition number of a matrix.

3. Consider the structure of the matrix: As you mentioned, your matrix has a specific structure, which may provide some insights into its condition number. For example, the presence of Vandermonde matrices in the second summand may have an impact on the overall condition number. It would be helpful to analyze the individual condition numbers of each summand and see how they affect the overall condition number.

4. Use a systematic approach: As you mentioned, brute forcing all possible subsets to find the one with the lowest condition number is not feasible. Instead, you can use a systematic approach such as gradient descent or genetic algorithms to search for the optimal subset of rows that minimizes the condition number. These methods can help you narrow down the search space and find a near-optimal solution.

I hope these pointers will help guide your analysis. Good luck with your research! If you have any further questions or need more specific guidance, please do not hesitate to reach out. As scientists, we are always happy to help and collaborate on challenging problems.

Best regards,