Sunday, April 16, 2006

Matrix Approximation

I went through a phase in college when I had a preference for looking at problems through the linear-algebra lens. In the past two years, I have been looking at data that has a nice matrix form where rows are subjects and columns are attributes. The matrix is large and I need a summary in order to understand it. The typical way to do this is to get a low-rank approximation which will give a few "directions" for an analyst to peer at, but unfortunately, these directions are linear combinations of the column (or row) space and typically, it is hard to understand intuitively what they represent. It will be incredibly useful if one could find original columns or rows that summarized the matrix.

In the past few months, Petros Drineas, Michael Mahoney and I have worked on formulating this problem and solving it. Given matrix A, we are able to quickly find poly-k columns C (or rows or both) such that a matrix A_C obtained from these columns is a (1+\eps) approximation to best k-rank matrix A_k for A. Formally, ||A-A_C|| <= (1+\eps)||A-A_k||. The columns C then is a useful set of attributes for an analyst to understand and interpret. The technical result is here from November 2005. ||.|| is the Frobenius norm.

There is a somewhat related problem in theory community: how to approximate A_k? The A_k that minimizes ||A-A_k|| is given immediately by SVD. In theory, Alan Frieze, Ravi Kannan and Santosh Vempala asked if this could be approximated in a few passes. Since then, a lot of published work has shown how to get a matrix representation A' of A such that ||A-A'||<= ||A-A_k|| +\eps ||A||. This large additive error is discouraging and the question that remained open was, are there relative error approximations in few passes or in time less than it takes to solve the SVD? My result with Petros and Michael above provides such a matrix representation, but takes time to find largest k exact or approximate left-singular values, which can be done in O(k) passes using methods in Numerical Analysis. I mentioned my result above to Sariel Har-Peled at FSTTCS 2006 in India; at that time, he promised he can produce an A' such that ||A-A'||<= (1+\eps) ||A-A_k||. He delivered: his writeup is here. This does not seem to address the problem Petros, Michael and I worked on since it does not output original columns or rows, but produces linear combinations. Quite recently, Amit Deshpande and Santosh Vempala obtained a similar result but focused on using a small number -- O(klog k) -- passes, in some sense culminating a long line of research on low rank approximation using a small number of passes. It seems we can derive another solution to our problem from their result.

Summary: We are in a better place than we were a year ago when only additive approximations were known for low-rank matrix summaries. Both problems now have relative error approximations in near-linear time. And the fun part is, each of these results use a different technique. Bonanza! Those who are interested should look at these papers since there are many details.

20 Comments:

Anonymous Anonymous said...

The approach of Har-Peled is essentially identical to
the one in the SODA 2006 paper by Deshpande et al.
(they call it adaptive sampling).

5:43 PM  
Anonymous Anonymous said...

I really enjoyed looking at your site, I found it very helpful indeed, keep up the good work.
»

9:53 PM  
Anonymous Anonymous said...

Nice! Where you get this guestbook? I want the same script.. Awesome content. thankyou.
»

1:29 AM  
Anonymous Anonymous said...

Hello All. Don't delete please!
stress relief
stress relief and relaxation technique
natural stress relief
stress relief tip
stress relief technique
stress relief product
herbal stress relief
relagen
Thanks.

1:57 PM  
Anonymous Anonymous said...

Wazzup people. Let's take a look. A great sollution for you.
hemorrhoids relief
hemorrhoids pain relief
hemorrhoids relief treatment
venapro
review venapro
hemorrhoids herbal treatment
stop smoking aid
nicocure
nicocure patch
stop smoking
stop smoking aids
stop smoking drug
stop smoking medicine
stop smoking patch
meds to stop smoking
new stop smoking drug
stop smoking product
stop smoking treatment
Don't delete this. Thanks!

9:51 PM  
Anonymous Anonymous said...

Halo people. Let's take a look. A great sollution for you.
hair removal
body hair removal
hair removal product
permanent hair removal at home
facial hair removal
permanent pubic hair removal
permanent body hair removal
facial hair removal product
nair hair removal product
permanent hair removal product for man
pubic hair removal product
prescription facial hair removal
hair removal for man
bikini hair removal
cream hair permanent removal
best cream hair removal
cream hair removal revitol
cream face hair removal
Don't delete this. Thanks!

10:41 PM  
Anonymous Anonymous said...

Wazzup All. Let's take a look. A great sollution for you.
pheromone spray
pheromone
human pheromone
pheromone perfume
buy pheromone
best pheromone
male pheromone
pheromone woman
man pheromone cologne
female pheromone
pheromone product
natural pheromone
human pheromone perfume
pheromone attract
human pheromone cologne
pheromone lotion
cheap pheromone
attract mate
pheromone spray
pheromone
human pheromone
pheromone perfume
buy pheromone
best pheromone
male pheromone
pheromone woman
man pheromone cologne
female pheromone
pheromone product
natural pheromone
human pheromone perfume
pheromone attract
human pheromone cologne
pheromone lotion
cheap pheromone
attract mate
Don't delete this. Thanks!

12:35 AM  
Anonymous Anonymous said...

Wazzup people. Let's take a look. A great sollution for you.
stress relief
stress relief technique
natural stress relief
stress relief tip
stress relief product
stress and anxiety relief
link relief stress suggest
herbal stress relief
natural stress anxiety relief
relief stress week working
herbs for stress relief
relief sex stress
stress headache relief
stress relief medication
relagen
relagen review
stress relief
stress relief technique
natural stress relief
stress relief tip
stress relief product
stress and anxiety relief
link relief stress suggest
herbal stress relief
natural stress anxiety relief
relief stress week working
herbs for stress relief
relief sex stress
stress headache relief
stress relief medication
relagen
relagen review
Don't delete this. Thanks!

2:23 PM  
Anonymous Anonymous said...

Halo people. Watch. A great sollution for you.
herbal treatment
herbal health
natural herbal medicine
acne herbal medicine
best acne treatment
natural acne treatment
hemorrhoids relief treatment
stop smoking
lower back pain relief
chronic pain relief
hair removal product
permanent hair removal at home
hgh supplement
hgh product
human pheromone
pheromone perfume
natural stress relief
stress relief tip
Don't delete this. Thanks!

7:55 PM  
Anonymous Anonymous said...

Hi
casey hay
young kat
bobbi eden
gauge samantha
crissy moran
crissy moran clip
lonnie water
natalia cruze
angel eve
angel ass eve
dakota patrick rae
jena kay ricci
suzanne winter
aimee sweet
tawny roberts cum
kira eggers
malaya rae
cherry potter pussy
vanessa blue
vanessa blue sex
sweet amylee
Bye

7:07 AM  
Anonymous Anonymous said...

Hi All. Take a look. A lot of fantastish beautifull womans.
princess cameron
nikky blonde
lucy summer
gauge samantha
crissy moran
crissy moran clip
jesse capelli
daniel lisa
laren shay
terri summers
diamond mya
rachel aziani
mandi rose fanelli
tawny roberts
gianni taylor
ashley simply
kaylani lei
cherry potter
christine young
christine young porn video
kelly summer
melissa doll
I like them. Don't delete this. Thanks!

7:20 AM  
Anonymous Anonymous said...

Hi
casey hay
young kat
bobbi eden
gauge samantha
crissy moran
crissy moran clip
lonnie water
natalia cruze
angel eve
angel ass eve
dakota patrick rae
jena kay ricci
suzanne winter
aimee sweet
tawny roberts cum
kira eggers
malaya rae
cherry potter pussy
vanessa blue
vanessa blue sex
sweet amylee
Bye

6:43 PM  
Anonymous Anonymous said...

Hello. Very interesting, really!
http://phentermine.alldating.org/phentermine.htm phentermine
phentermine online
phentermine
http://phentermine.alldating.org/buy-phentermine.htm buy phentermine
buy phentermine
buy phentermine
http://phentermine.alldating.org/buy-phentermine.htm
buy phentermine
cheap phentermine
Its'not a spam, help sick children! I am very sorry!

12:27 AM  
Anonymous Anonymous said...

Hi. Very interesting, really!
cheap phentermine
Don't delete. Help homeless children, thanks

10:10 PM  
Blogger boon said...

I don't know if this is related. Given a fix vector x, I want to find a matrix A such that A^(-1)P A x is a minimum. where P is a projection matrix into a smaller subspace of dimension k. And Oh, I forgot to mention that A has to live in SO(n). Looks like a minimum/maximum problem but it probably requires some rewording.

8:08 AM  
Anonymous thin hair said...

black mold exposureblack mold symptoms of exposurewrought iron garden gatesiron garden gates find them herefine thin hair hairstylessearch hair styles for fine thin hairnight vision binocularsbuy night vision binocularslipitor reactionslipitor allergic reactionsluxury beach resort in the philippines

afordable beach resorts in the philippineshomeopathy for eczema.baby eczema.save big with great mineral makeup bargainsmineral makeup wholesalersprodam iphone Apple prodam iphone prahacect iphone manualmanual for P 168 iphonefero 52 binocularsnight vision Fero 52 binocularsThe best night vision binoculars here

night vision binoculars bargainsfree photo albums computer programsfree software to make photo albumsfree tax formsprintable tax forms for free craftmatic air bedcraftmatic air bed adjustable info hereboyd air bedboyd night air bed lowest pricefind air beds in wisconsinbest air beds in wisconsincloud air beds

best cloud inflatable air bedssealy air beds portableportables air bedsrv luggage racksaluminum made rv luggage racksair bed raisedbest form raised air bedsaircraft support equipmentsbest support equipments for aircraftsbed air informercialsbest informercials bed airmattress sized air beds

bestair bed mattress antique doorknobsantique doorknob identification tipsdvd player troubleshootingtroubleshooting with the dvd playerflat panel television lcd vs plasmaflat panel lcd television versus plasma pic the bestThe causes of economic recessionwhat are the causes of economic recessionadjustable bed air foam The best bed air foam

hoof prints antique equestrian printsantique hoof prints equestrian printsBuy air bedadjustablebuy the best adjustable air bedsair beds canadian storesCanadian stores for air beds

migraine causemigraine treatments floridaflorida headache clinicdrying dessicantair drying dessicantdessicant air dryerpediatric asthmaasthma specialistasthma children specialistcarpet cleaning dallas txcarpet cleaners dallascarpet cleaning dallas

5:14 AM  
Blogger adelen said...

There is now a new quit smoking drug available in the market. This latest breakthrough is known as Chantix. It is able to help smokers snub out their addiction by working on the brain.

10:23 PM  
Blogger hannah said...

I lost a lot of weight by taking Phentermine that I ordered from WWW.MEDSHEAVEN.COM i am very satisfied!

9:37 PM  
Blogger chantix said...

Do you know why chantix is so popular for quite smoking. Because it gives very good results and FDA approved Chantix Pill for Quit smoking !

5:09 AM  
Anonymous Mobile Application said...

My friend recommended to this blog.... you have some awesome articles shear. keep it up the great work

android application | android web application

5:18 AM  

Post a Comment

<< Home