User ismail arı - MathOverflow

Proof of a fact about traces

2011-02-27T16:40:13Z

I'm following the open courseware content on Machine Learning from Stanford University. In the lecture notes, it is given that

$$\Delta_A \ tr(ABA^TC) = CAB + C^TAB^T$$

which I tried but couldn't prove easily. It is not required to follow the course content but I just wondered and wanted to learn its proof. Any suggestions?

Update: $A$, $B$, and $C$ are matrices and $\Delta_A$ is the gradient operation on matrix $A$.

Making MATLAB svd robust to transpose operation

2010-10-11T07:42:29Z

I'm playing with MATLAB's svd function to compute the svd of

 [ 1     4     7    10
   2     5     8    11
   3     6     9    12 ]

When I type [U1, ~, ~] = svd(X), I get

U1 =

 -0.5045    0.7608    0.4082
 -0.5745    0.0571   -0.8165
 -0.6445   -0.6465    0.4082

But when I compute the svd of the transpose of X with [~, ~, U2] = svd(X'), I get

U2 =

  0.5045    0.7608    0.4082
  0.5745    0.0571   -0.8165
  0.6445   -0.6465    0.4082

The first singular vectors seem to be pointing to the opposite directions but the others are the same. I know that svd is not unique and the solution is correct because the first component of V1 and V2 are pointing opposite directions as well. But, I would expect MATLAB to return the same answers. I thought to add a postprocessing and check the singular vector pairs and turn their directions to make them consistent under transpose but I couldn't find a mathematically reasonable way of doing it.

Do you know why MATLAB (or LAPACK as it says MATLAB uses LAPACK) computes this way? Do you have any suggestions how to make it consistent? Thanks.

Update: the reason I ask for it is that I wanted to see what happens if I apply higher order singular value decomposition (HOSVD) to 2 dimensional matrices. In theory, it holds. Using the same mathematical notation, SVD is formulated as follows:

Every $\mathbf{X} \in \mathbb{C}^{I_1 \times I_2}$ can be written as the product

.$$\mathbf{X} = \mathbf{U}^{(1)} \cdot \mathbf{S} \cdot \mathbf{U}^{(2)^H} = \mathbf{S} \times_1 \mathbf{U}^{(1)} \times_2 \mathbf{U}^{(2)}$$

in which

$\mathbf{U}^{(1)} = \left[ \begin{array}{cccc} U_{1}^{(1)} & U_{2}^{(1)} & \dots & U_{I_1}^{(1)} \end{array} \right] \in \mathbb{C}^{I_1\times I_1}$ is unitary.

$\mathbf{U}^{(2)} = \left[ \begin{array}{cccc} U_{1}^{(2)} & U_{2}^{(2)} & \dots & U_{I_I}^{(2)} \end{array} \right] \in \mathbb{C}^{I_2\times I_2}$ is unitary.

$\mathbf{S} \in \mathbb{C}^{I_1\times I_2}$ has the the following properties:

pseudodiagonality: $\newcommand{\diag}{\mathop{\mathrm{diag}}} \mathbf{S} = \diag\left(\ \sigma_1, \sigma_2, \dots, \sigma_{\min(I_1,I_2)} \right)$
ordering: $\sigma_1 \geq \sigma_2 \geq \ldots \geq \sigma_{\min(I_1, I_2)} \geq 0$

So, to compute it I found the right and singular vectors as if they were computed independently because I want to extend it to multidimensions later. To compute them independently, I calculated the eigenvalues of $\mathbf{XX'}$ and $\mathbf{X'X}$ as follows:

[U{1}, ~] = eig(X*X');
U{1} = fliplr(U{1});
[U{2}, ~] = eig(X'*X);
U{2} = fliplr(U{2});

but they seem to be as I explained above. Actually, it doesn't effect what I need but I would like to make the singular values positive. This way, they might become negative since the right and left singular vectors are not as I expected.

Update 2: Alternatively, I used the code with svd() function as below and it gives similar results. With the 'econ' option, only min(nDim1,nDim2) singular vectors are returned and I set the remaining as 0 vector. The economy option (i.e. computing the non-zero vectors makes it practical when the higher order matrices [n-way arrays] are turned into matrices and svd is applied to them.)

[U{1}, ~, ~] = svd(X, 'econ');
U{1} = [U{1} zeros(size(U{1},1), size(U{1},1)-size(U{1},2))];
[U{2}, ~, ~] = svd(X', 'econ');
U{2} = [U{2} zeros(size(U{2},1), size(U{2},1)-size(U{2},2))];

How do eigenvectors and eigenvalues change when we remove a row/column pair of a matrix?

2010-10-25T13:18:49Z

Let us have a symmetric matrix $C \in \mathbb{R}^{n\times n}$ having non-negative values. Suppose that we have the eigenvalue decomposition for this particular matrix such that

$$C e_i = \lambda_i e_i$$

where $e_i$ are the eigenvectors and $\lambda_i \geq 0$ are the corresponding eigenvalues. In matrix form,

$$CE = ES$$ where $E$ is the matrix involving eigenvectors as columns and $S$ is the diagonal matrix involving eigenvalues on the diagonal entries.

Now, we delete $k^\text{th}$ row and column of the matrix and form a new matrix $\tilde{C} \in \mathbb{R}^{(n-1) \times (n-1)}$ and we want to find its eigenvalues and eigenvectors such that

$$\tilde{C} \tilde{E} = \tilde{E} \tilde{S}$$

Instead of computing them from scratch, I wonder if there exists an analytical way to find the eigenvectors and eigenvalues iteratively using $E$ and $S$. In other words, is there a link between $E$, $S$ and $\tilde{E}$, $\tilde{S}$?

For example, for a 3-by-3 matrix $C$ where

$$C = \left[\begin{array}{ccc}a & b & c \\ b & d & e \\ c & e & f\end{array}\right]$$

if I delete the third row and column, then I get

$$C = \left[\begin{array}{cc}a & b \\ b & d \end{array}\right]$$

I know that the number of dimensions of the eigenvectors are one less and we have one less eigenvalues but may there be a projection of the others onto some bases?

P.S.(1) I've read the answers to the question "How does eigenvalues and eigenvectors change if the original matrix changes slightly", but I couldn't find a connection with this question. Sorry if I couldn't get a point and created a duplicate question.

P.S.(2) If you wonder why I'm asking this question, here it is: I'm computing the eigenvalues and eigenvectors of the covariance matrix of some samples. Let each sample have 3 dimensions and let $D \in \mathbb{R}^{k\times n}$ be the data matrix where each row is a sample and we have $k$ samples. Then the covariance matrix is $C = D^T D$. If we have 3 dimensions and the columns of $D$ are $d_1$, $d_2$ and $d_3$, then we have

$$ C = \left[\begin{array}{ccc}d_1^T d_1 & d_1^T d_2 & d_1^T d_3 \\ d_2^T d_1 & d_2^T d_2 & d_2^T d_3 \\ d_3^T d_1 & d_3^T d_2 & d_3^T d_3\end{array}\right]$$

I'm interested in the decomposition when we have some dimensions missing in the data. If, as in the example, the third dimension is missing, then we have

$$ \tilde{C} = \left[\begin{array}{cc}d_1^T d_1 & d_1^T d_2 \\ d_2^T d_1 & d_2^T d_2 \end{array}\right]$$

I wondered whether there's a way to compute the eigenvectors and eigenvalues of the missing data's covariance matrix using the ones that we computed from the full data in an iterative manner instead of computing it from scratch.

Kind regards and thanks for any ideas.

Why do we want to have orthogonal bases in decompositions?

2010-10-13T17:52:24Z

In the decompositions I encountered so far, we all had orthogonal set of bases. For example in Singular Value Decomposition, we had orthogonal singular right and left vectors, in [discrete] cosine transform (or [discrete] fourier transform) we had again orthogonal bases.

To describe any vector $x \in \mathbb{C}^N$, we need to have $N$ independent set of basis vectors but independent doesn't necessarily mean orthogonal. My intentions behind selecting orthogonal vectors are as follows:

The solution is not unique for $x$ if the basis are not orthogonal.
It is easy to find the solution numerically by projecting $x$ onto each vector and this solution doesn't depend on the order of the bases. Otherwise, it depends on the order.
If we are talking about some set of vectors, they might be correlated in the original space, but uncorrelated in the transformd space which might be important when analyzing the data, in dimensionality reduction or compression.

I'm trying to understand the big picture. Do you think that I am right with these? Do you have any suggestions, what is the main reason for selecting orthogonal bases?

Comment by İsmail Arı

2011-04-11T08:27:44Z

Thanks for the warning. I updated the question.

Comment by İsmail Arı

2011-04-10T23:23:59Z

I don't see the reason for getting a -1 for the question. Is that because I couldn't prove it easily? If so, why are there 8 current upvotes for the answer post. If I know the reason, I would update my questioning to mathoverflow community accordingly.

Comment by İsmail Arı

2011-02-27T17:14:20Z

Dear Fabian: Your guess is correct. Sorry for missing definition. The operator in question is the gradient operation as you guessed.

Comment by İsmail Arı

2011-02-27T17:07:57Z

Dear Todd: Thanks for you advice. I will take your remarks about how to ask a question into consideration. The course notes are here: stanford.edu/class/cs229/notes/cs229-notes1.pdf Page 9, Eq. 3.

Comment by İsmail Arı

2010-11-17T09:31:32Z

I have checked most of your papers but missed this one. Thank you for your kind response.

Comment by İsmail Arı

2010-10-14T19:45:26Z

I think I understood the mathematical way of seeing vectors. I always thought of them as being a bunch of numbers actually because of my engineering-oriented education. Thank you for the additional explanation.

Comment by İsmail Arı

2010-10-14T13:18:08Z

Actually, the scalar products always be +/-1. I couldn't understand clearly how to do a normalization on comparison operator. The trick is to not to compute all svd but solve it partially. I tried and added another piece of code into the question where I used svd() function with economic usage, where it finds only min(M,N) singular vectors. The significant vectors again do not fit in sign.

Comment by İsmail Arı

2010-10-14T13:08:53Z

Sorry, I forgot to mention. Yes, I did. I updated the code in the question.

Comment by İsmail Arı

2010-10-14T10:25:24Z

@Darsh Yes, you are definitely right. I don't know how it is computed in the background but at least for this one, it would be great to have the same results. @Federico I added the reason in the question.

Comment by İsmail Arı

2010-10-14T10:22:43Z

When I find the largest valued vector, they I think your suggestion is to multiply the directions with -1. But again the vectors do not fit as in the example solution in the question. Do you have any other suggestion to do after finding this large valued vector.

Comment by İsmail Arı

2010-10-14T09:41:42Z

Thank you for the simple proof for my first point. You are definitely right. I didn't think on it clearly and accepted it as correct when a a friend of mine told that it should be that way. For the third point, I will check what spectral theorem gives us. Actually, the correlation/dependence was in my mind because of principal component analysis which is close to singular value decomposition. For example, it this image (bit.ly/cyt22i), when we change the bases, the data becomes independent (but for this gaussian distributed samples in fact). Is correlation independent from the bases?

Comment by İsmail Arı

2010-10-11T12:29:07Z

Yes, I've. It seems to show a similar pattern. The first singular vectors are in opposite signs but the second and the third ones are the same as expected.