NDLI: Fast computation of low rank matrix approximations

Please wait, while we are loading the content...

Clustering to minimize the sum of cluster diameters

Approximating min-sum k-clustering in metric spaces

Local search heuristic for k-median and facility location problems

Profit-earning facility location

One-dimensional quantum walks

Quantum walks on graphs

Quantum algorithms for solvable groups

Quantum mechanical algorithms for the nonabelian hidden subgroup problem

Minimax parametric optimization problems and multi-dimensional parametric searching

Algorithms for minimizing weighted flow time

Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

Stackelberg scheduling strategies

Quantum computers that can be simulated classically in polynomial time

Interaction in quantum communication and the complexity of set disjointness

A new protocol and lower bounds for quantum coin flipping

Loss-less condensers, unbalanced expanders, and extractors

Conditions on input vectors for consensus solvability in asynchronous distributed systems

Spatial gossip and resource location protocols

(1 + εΒ)-spanner constructions for general graphs

Approximate distance oracles

Extractor codes

Excellent codes from modular curves

Sparse polynomial approximation in finite fields

Randomness efficient identity testing of multivariate polynomials

Fully-dynamic min-cut

Computing crossing numbers in quadratic time

Euler paths in series parallel graphs

Decidability of string graphs

Learning mixtures of arbitrary gaussians

Learning DNF in time

Sampling algorithms: lower bounds and applications

Testing metric properties

Testing of matrix properties

Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

One line and ε

A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

Lower bounds for intersection searching and fractional cascading in higher dimension

Sharp threshold and scaling window for the integer partitioning problem

A sharp threshold in proof complexity

Regular resolution lower bounds for the weak pigeonhole principle

The complexity of analytic tableaux

Applications of approximation algorithms to cooperative games

Approximation algorithms for constrained for constrained node weighted steiner tree problems

A constant factor approximation for the single sink edge installation problems

Provisioning a virtual private network: a network design problem for multicommodity flow

Explicit lower bound of 4.5n - o(n) for boolena circuits

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

A read-once branching program lower bound of $Ω(2^{n/4})$ for integer multiplication using universal hashing

On the cell probe complexity of membership and perfect hashing

On the integrality ratio of semidefinite relaxations of MAX CUT

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming

Non-approximability results for optimization problems on bounded degree instances

Colouring graphs when the number of colours is nearly the maximum degree

Data-streams and histograms

Optimal static range reporting in one dimension

Biased dictionaries with fast insert/deletes

Anti-persistence: history independent data structures

Dynamic TCP acknowledgement and other stories about e/(e-1)

The price of selfish routing

Buffer overflow management in QoS switches

Almost optimal permutation routing on hypercubes

Online server allocation in a server farm via benefit task systems

Private approximation of NP-hard functions

Concurrent and resettable zero-knowledge in poly-loalgorithm rounds

Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds

The round complexity of verifiable secret sharing and secure multicast

Communication preserving protocols for secure function evaluation

Some perspectives on computational complexity

A sieve algorithm for the shortest lattice vector problem

Fast computation of low rank matrix approximations

Spectral analysis of data

Optimal outlier removal in high-dimensional

Estimating true evolutionary distances between genomes

On optimal slicing of parallel programs

When is the evaluation of conjunctive queries tractable?

The complexity of maximal constraint languages

Quantitative solution of omega-regular games380872

Distribution functions of probabilistic automata

Compatible sequences and a slow Winkler percolation

Edge isoperimetry and rapid mixing on matroids and geometric Markov chains

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

Computing with continuous-time Liapunov systems

Complex tilings

Running time and program size for self-assembled squares

Algorithms, games, and the internet

Automata, circuits and hybrids: facets of continuous time

Fast computation of low rank matrix approximations

Content Provider	ACM Digital Library
Author	Achlioptas, Dimitris McSherry, Frank
Abstract	Given a matrix A it is often desirable to find an approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong spectral structure, i.e., when the singular values of interest are significantly greater than those of a random matrix with size and entries similar to A. Our technique amounts to independently sampling and/or quantizing the entries of A, thus speeding up computation by reducing the number of non-zero entries and/or the length of their representation. Our analysis is based on observing that the acts of sampling and quantization can be viewed as adding a random matrix E to A, whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, E has very weak spectral structure, we can prove that the effect of sampling and quantization nearly vanishes when a low rank approximation to A+E is computed. In fact, the stronger the spectral structure of A, the more of its entries we can afford to discard and, ultimately, the faster we can discover that structure. We give bounds on the quality of our approximation both in the L2 and in the Frobenius norm.
Starting Page	611
Ending Page	618
Page Count	8
File Format	PDF
ISBN	1581133499
DOI	10.1145/380752.380858
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-07-06
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in