  We propose LSDAT, an image-agnostic decision-based black-box attack that
exploits low-rank and sparse decomposition (LSD) to dramatically reduce the
number of queries and achieve superior fooling rates compared to the
state-of-the-art decision-based methods under given imperceptibility
constraints. LSDAT crafts perturbations in the low-dimensional subspace formed
by the sparse component of the input sample and that of an adversarial sample
to obtain query-efficiency. The specific perturbation of interest is obtained
by traversing the path between the input and adversarial sparse components. It
is set forth that the proposed sparse perturbation is the most aligned sparse
perturbation with the shortest path from the input sample to the decision
boundary for some initial adversarial sample (the best sparse approximation of
shortest path, likely to fool the model). Theoretical analyses are provided to
justify the functionality of LSDAT. Unlike other dimensionality reduction based
techniques aimed at improving query efficiency (e.g, ones based on FFT), LSD
works directly in the image pixel domain to guarantee that non-$\ell_2$
constraints, such as sparsity, are satisfied. LSD offers better control over
the number of queries and provides computational efficiency as it performs
sparse decomposition of the input and adversarial images only once to generate
all queries. We demonstrate $\ell_0$, $\ell_2$ and $\ell_\infty$ bounded
attacks with LSDAT to evince its efficiency compared to baseline decision-based
attacks in diverse low-query budget scenarios as outlined in the experiments.
