Timeline for Sparse matrix approximation using only a few dense columns (or rows)
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 29, 2017 at 12:00 | comment | added | Federico Poloni | ($A-A_I$ in the LHS, not $A-I$, sorry.) | |
| May 29, 2017 at 9:18 | comment | added | Federico Poloni | Isn't this answer killing flies with cannons? $\|A-I\|^2_F = \sum_{i \not \in I} \|a_i\|^2$, where $a_i$ are the rows of $A$, so it seems clear that the solution is taking the rows with maximum norms. | |
| May 29, 2017 at 8:46 | comment | added | Rodrigo de Azevedo | If the goal is to minimize the squared Frobenius norm, why worry if two rows are linearly dependent? There are no constraints on the rank, are there? | |
| May 29, 2017 at 8:42 | comment | added | Paul Irofti | Whereas an iterative algorithm would pick the largest 2-norm row, and then pick the 2nd row whose orthogonal projection on the current residual is largest. And so on, and so forth. This is the OMP approach for matrices instead of vectors, which is what I expected out of Smola's paper that I cited in my question. | |
| May 29, 2017 at 8:42 | comment | added | Paul Irofti | I reached the same result initially, but I think that using an iterative algorithm that attempts to maximize the residual minimization at each step makes more sense in this scenario then picking the largest $s$ rows. My reasoning is as follows, say we select 2 largest 2-norm rows. Each row on its own will surely have a large impact on reducing the residual. But once I select the largest row, the second largest might not continue to be the most important row because the two rows might be pointing in the same direction. | |
| May 27, 2017 at 16:42 | history | edited | Rodrigo de Azevedo | CC BY-SA 3.0 |
Added conclusion
|
| May 27, 2017 at 15:33 | history | edited | Rodrigo de Azevedo | CC BY-SA 3.0 |
Fixed typo
|
| May 27, 2017 at 15:15 | history | answered | Rodrigo de Azevedo | CC BY-SA 3.0 |