Sharp Guarantees for Solving Random Equations with One-Bit Information
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis Electrical and Computer Engineering Department, University of California, Santa Barbara, Santa Barbara, CA 93106, USA. Emails: {hossein, ramtin,
Abstract
We study the performance of a wide class of convex optimization-based estimators for recovering a signal from corrupted one-bit measurements in high-dimensions. Our general result predicts sharply the performance of such estimators in the linear asymptotic regime when the measurement vectors have entries IID Gaussian. This includes, as a special case, the previously studied least-squares estimator and various novel results for other popular estimators such as least-absolute deviations, hinge-loss and logistic-loss. Importantly, we exploit the fact that our analysis holds for generic convex loss functions to prove a bound on the best achievable performance across the entire class of estimators. Numerical simulations corroborate our theoretical findings and suggest they are accurate even for relatively small problem dimensions.
中文速览
在高维场景下，仅凭一比特（one-bit）量测值（即每条观测只保留符号正负）来还原未知信号是一个极具挑战性的问题，已有研究大多只给出精度较粗的量级估计，且主要局限于最小二乘这一种估计方法。本文针对一大类基于凸优化的估计器——包括最小二乘、最小绝对偏差（LAD）、铰链损失（hinge-loss）和逻辑回归等——在测量向量服从独立同分布高斯假设下，利用凸高斯极小极大定理（CGMT）建立了一套精确的渐近分析框架：当测量数 $m$ 与维度 $n$ 按固定比例同时趋于无穷时，估计器与真实信号之间的相关性可由一组仅含三个未知数的非线性方程组精确刻画，而方程组的形式完全由损失函数的 Moreau 包络决定。借助这一统一框架，作者不仅重新导出了已有的最小二乘结果，还首次给出了其他多种估计器的精确性能公式，并进一步推导出在全部凸损失函数中可达相关性的理论上界，从而为寻找最优损失函数提供了依据。数值实验表明，即便在几百维的中等规模问题上，理论预测与仿真结果也高度吻合，说明该渐近结论在实践中具有很强的实用价值。
原文 arXiv:1908.04433;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1908.04433v2