Ted, please blog this. No rewrites required.
On Sun, Dec 12, 2010 at 9:53 PM, Ted Dunning <ted.dunning@gmail.com> wrote:
> Ahh...
>
> In fact, dimensional reduction algorithms do not change the size of the
> matrix being approximated. Instead, they approximate the matrix by
> considering each user and each item to have a reduced dimensional
> representation. This is represented by the matrix product A \approx U D V'.
> Here the user x item matrix A is approximated by user vectors U, item
> vectors V (transposed) and a diagonal weighting matrix that allows columns
> of U and V to be normalized. If U and V have only a limited number of
> columns, then this can only be an approximation of A. A capital sigma is
> often used instead of a D.
>
> The accuracy of the approximation is generally described in terms of the
> norm of A  U D V'. This norm can be any of many norms. One useful one is
> the Frobenius norm which is the sum of the squares of a matrix. Another is
> the 2norm which is the maximum amount that the matrix can cause a vector to
> grow. All of the norms that involves squares like Frobenius and 2norm are
> closely related to the squared magnitudes of the elements of D.
>
> Conceptually, a matrix A can be decomposed exactly using full dimension
> (rank) for U and V. In this case A = U D V' so there is no
> error. A nice thing about the singular value decomposition is that D can be
> arranged in descending magnitude and the best reduced representation is
> found by simply setting the smallest values of D to zero. The quality of
> the reduced representation is directly related to the magnitudes of the
> missing values of D.
>
> So the answer to your question is yes. The quality can be quantified and
> reasonably easily by simply computing a few extra elements of D and looking
> at how quickly these are decreasing.
>
> That leaves the question of how well the random projection algorithm
> approximates the idealized decomposition. The practical answer here is that
> it almost certainly is very, very accurate.
>
> The remaining question is how well this reduced representation can be used
> to create a predictive model. That is a MUCH harder question to answer.
>
>
> On Sun, Dec 12, 2010 at 8:33 PM, Lance Norskog <goksron@gmail.com> wrote:
>
>> Should be "scalar or vector". I'm interested in the loss of precision
>> by dimensional reduction algorithms: matrix difference is only defined
>> for samesize matrices. So, there is no real absolute measure, just
>> relative measures that are not very useful except for certain use
>> cases.
>>
>> On Sun, Dec 12, 2010 at 7:21 PM, Ted Dunning <ted.dunning@gmail.com>
>> wrote:
>> > What do you mean by rank of a matrix? The normal definition is the
>> number
>> > of nonzero singular values. This
>> > doesn't sound like what you mean.
>> >
>> > What do you mean by loss of information? If you mean how do you compare
>> an
>> > approximation of a matrix
>> > versus the original, yes there are ways of doing that, not all very
>> useful.
>> > Norm of the difference is one example
>> > that leads to least squares formulations.
>> >
>> > Also, is there something missing from the sentence with "scalar of
>> vector"
>> > in it?
>> >
>> > On Sun, Dec 12, 2010 at 6:04 PM, Lance Norskog <goksron@gmail.com>
>> wrote:
>> >
>> >> Given a matrix reduction algorithm, how do you measure the loss of
>> >> information perpetrated by the algorithm on the poor defenseless input
>> >> matrix?
>> >> Are there algorithms to compare two matrices and get a relative rank
>> value?
>> >>
>> >> Is there a scalar of vector that describes the rank of a matrix? Then
>> >> you could just compare the two rank values.
>> >>
>> >> Is there a probabilistic approach to the problem?
>> >>
>> >> 
>> >> Lance Norskog
>> >> goksron@gmail.com
>> >>
>> >
>>
>>
>>
>> 
>> Lance Norskog
>> goksron@gmail.com
>>
>

Lance Norskog
goksron@gmail.com
