NDLI: Robust subspace iteration and privacy-preserving spectral analysis

Content Provider	IEEE Xplore Digital Library
Author	Hardt, M.
Copyright Year	2013
Description	Author affiliation: IBM Res. Almaden, San Jose, CA, USA (Hardt, M.)
Abstract	We discuss a new robust convergence analysis of the well-known subspace iteration algorithm for computing the dominant singular vectors of a matrix, also known as simultaneous iteration or power method. The result characterizes the convergence behavior of the algorithm when a large amount noise is introduced after each matrix-vector multiplication. While interesting in its own right, the main motivation comes from the problem of privacy-preserving spectral analysis where noise is added in order to achieve the privacy guarantee known as differential privacy. This result leads to nearly tight worst-case bounds for the problem of computing a differentially private low-rank approximation in the spectral norm. Our results extend to privacy-preserving principal component analysis. We obtain improvements for several variants of differential privacy that have been considered. The running time of our algorithm is nearly linear in the input sparsity leading to strong improvements in running time over previous work. Complementing our worst-case bounds, we show that the error dependence of our algorithm on the matrix dimension can be replaced by a tight dependence on the coherence of the matrix. This parameter is always bounded by the matrix dimension but often much smaller. Indeed, the assumption of low coherence is essential in several machine learning and signal processing applications.
Sponsorship	IEEE Cont. Syst. Soc.
Starting Page	1624
Ending Page	1626
File Size	566580
Page Count	3
File Format	PDF
e-ISBN	9781479934102
DOI	10.1109/Allerton.2013.6736723
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-02
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Privacy Noise Coherence Vectors Robustness Sparse matrices
Content Type	Text
Resource Type	Article

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

Robust PCA with partial subspace knowledge

Fast Spectral Clustering with Landmark-Based Subspace Iteration

Iterative online subspace learning for robust image alignment

An Adaptive Projected Subgradient based algorithm for robust subspace tracking

Recursive robust PCA or recursive sparse recovery in large but structured noise

Robust adaptive beamforming via sparse covariance matrix estimation and subspace projection

Randomized robust subspace recovery for big data

Robust and sparse estimation of tensor decompositions

A robust online subspace estimation and tracking algorithm

Robust subspace iteration and privacy-preserving spectral analysis

Similar Documents

Robust PCA with partial subspace knowledge

Fast Spectral Clustering with Landmark-Based Subspace Iteration

Iterative online subspace learning for robust image alignment

An Adaptive Projected Subgradient based algorithm for robust subspace tracking

Recursive robust PCA or recursive sparse recovery in large but structured noise

Robust adaptive beamforming via sparse covariance matrix estimation and subspace projection

Randomized robust subspace recovery for big data

Robust and sparse estimation of tensor decompositions

A robust online subspace estimation and tracking algorithm

Robust subspace iteration and privacy-preserving spectral analysis