## Abstract

We present a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, an important and well-studied setting for independent component analysis (ICA). Specifically, given an ϵ-corrupted sample from a distribution D obtained by applying an unknown affine transformation x → A x+b to the uniform distribution on a d-dimensional hypercube [-1,1]d, our algorithm constructs A, b such that the total variation distance of the distribution D from D is O(ϵ) using poly (d) time and samples. Total variation distance is the information-theoretically strongest possible notion of distance in our setting and our recovery guarantees in this distance are optimal up to the absolute constant factor multiplying ϵ. In particular, if the rows of A are normalized to be unit length, our total variation distance guarantee implies a bound on the sum of the ℓ_2 distances between the row vectors of A and A′, ∑_i=1d||a_(i)-a_(i)||_2=O(ϵ). In contrast, the strongest known prior results only yield an ϵO(1) (relative) bound on the distance between individual a_i's and their estimates and translate into an O(d ϵO(1)) bound on the total variation distance.Prior algorithms for this problem rely on implementing standard approaches [12] for ICA based on the classical method of moments [18], [32] combined with robust moment estimators. We prove that any approach that relies on method of moments must provably fail to obtain a dimension independent bound on the total error ∑_i||a_(i)-a_(i)||_2 (and consequently, also in total variation distance). Our key innovation is a new approach to ICA (even to outlier-free ICA) that circumvents the difficulties in the classical method of moments and instead relies on a new geometric certificate of correctness of an affine transformation. Our algorithm, Robust Gradient Descent, is based on a new method that iteratively improves its estimate of the unknown affine transformation whenever the requirements of the certificate are not met.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023 |

Publisher | IEEE Computer Society |

Pages | 2408-2429 |

Number of pages | 22 |

ISBN (Electronic) | 9798350318944 |

DOIs | |

State | Published - 2023 |

Externally published | Yes |

Event | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, United States Duration: Nov 6 2023 → Nov 9 2023 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN (Print) | 0272-5428 |

### Conference

Conference | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 |
---|---|

Country/Territory | United States |

City | Santa Cruz |

Period | 11/6/23 → 11/9/23 |

## All Science Journal Classification (ASJC) codes

- General Computer Science

## Keywords

- Affine Transformation
- Independent Component Analysis
- Method of Moments
- Robust Statistics