# Can We Find a More Sparse $S$?

### Original question

I am working with a sparse matrix $$S$$ with the assumption of sparsity such that in a matrix of $$N^2$$ elements, at most $$2N$$ are non-zero. (This sparsity condition could be adjusted if needed). I also assume $$S$$ is full rank. Let the singular value decomposition (SVD) of $$S$$ be given by

$$S = U \Lambda V^T$$

I am curious whether there exists a unitary matrix $$V'$$ such that $$S' = U \Lambda V'^T$$ results in a matrix $$S'$$ that is sparser than $$S$$. Here, "sparser" could mean having more zeros or a smaller L1 norm.

Alternatively, I am interested in understanding under what conditions such a matrix $$V'$$ does not exist. We could have more assumptions on $$S$$ to have some results.

Thanks to @Exodd, I've simplified my inquiry to whether there exists a unitary matrix $$U'$$ such that $$S' = S U'$$ results in a matrix $$S'$$ that is sparser than $$S$$. Here, "sparser" could mean having more zeros or a smaller L1 norm.

Actually, I am interested in understanding under what conditions such a matrix $$U'$$ does not exist. We could have more assumptions on $$S$$ to have some results. The assumption now I have is $$diag(S)=1$$

This question may seem open-ended or not strict, and I apologize if it appears foolish. I am looking forward to any insights or references that could guide me on this topic.

### Update:

I have found some cases where a more sparse result can be achieved. However, my primary interest is in understanding under what conditions a more sparse result cannot be achieved.

For example, consider $$S = \begin{bmatrix} 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$$ and $$S' = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$$. Performing SVD on $$S$$ and $$S'$$, we find that both have the same $$U$$ and $$\Lambda$$, but different $$V$$ matrices. In particular:

$$S' = 1 \cdot [1 \ 0 \ 0]^T [0 \ 1 \ 0]$$

$$S = 1 \cdot [1 \ 0 \ 0]^T \left[\begin{array}{ccc} 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right]$$

• using a QR decomposition you can always bring any dense matrix in an upper rectangular one through multiplication by orthogonal matrices Commented Aug 1 at 13:57
• ps. changing $V$ does not change the product $SS^T$ and its sparsity should give you insight on the optimal sparsity Commented Aug 1 at 13:59
• @Exodd Thanks for your insightful response. But a upper rectangular matrix can be not sparser than S. Have assumptions on $SS^T$ might be a good idea. Commented Aug 1 at 14:08