Orthonormal Sketches for Secure Coded Regression

In this work, we propose a method for speeding up linear regression distributively, while ensuring security. We leverage randomized sketching techniques, and improve straggler resilience in asynchronous systems. Specifically, we apply a random orthonormal matrix and then subsample in $\mathit{\text{blocks}}$, to simultaneously secure the information and reduce the dimension of the regression problem. In our setup, the transformation corresponds to an encoded encryption in an $\mathit{\text{approximate}}$ gradient coding scheme, and the subsampling corresponds to the responses of the non-straggling workers; in a centralized coded computing network. We focus on the special case of the $\mathit{\text{Subsampled}}\mathit{\text{Randomized}}\mathit{\text{Hadamard}}\mathit{\text{Transform}}$, which we generalize to block sampling; and discuss how it can be used to secure the data. We illustrate the performance through numerical experiments.