Deep learning models are susceptible to contrived adversarial examples, even in the decision-based black-box setting where the attacker has access to the model’s decisions only. Developing more efficient and practical attacks help in better understanding the limitations of deep models. It is important that attacks are crafted with limited queries to avoid suspicion. Since the required number of queries increase with dimensions, low-dimensional embeddings are attractive. This low query budget constraint is a bottleneck for learning-based and data-driven attacks which rely heavily on querying the model. We propose LSDAT, an image-agnostic non-data-driven decision-based black-box attack that exploits low-rank and sparse decomposition (LSD) of images to dramatically reduce the queries and improve fooling rates compared to existing methods. LSDAT crafts perturbations in the low-dimensional subspace formed by the sparse component of the input image and that of a target adversarial image to obtain query-efficiency. A viable perturbation is obtained by traversing the path between the input and adversarial sparse components. Theoretical analyses are provided to justify the functionality of LSDAT. Unlike other competitors (e.g., FFT), LSD works directly in the image domain to guarantee that non-$\ell _{2}$constraints, such as sparsity, are satisfied. LSDAT offers better control over the number of queries and is computationally efficient as it performs sparse decomposition of the input and adversarial images only once to generate all queries. Four variants of LSDAT are presented for different scenarios including a pure black-box attack where no queries are allowed. We demonstrate$\ell _{0}$,$\ell _{2}$and$\ell _{\infty} $bounded attacks with LSDAT to evince its efficiency compared to baseline attacks in diverse low-query budget scenarios. LSDAT obtains 15 to 20% improvement in fooling ResNet-50 while using far fewer queries than competing methods in a similar setting.

Finding a small subset of data whose linear combination spans other data points, also called column subset selection problem (CSSP), is an important open problem in computer science with many applications in computer vision and deep learning. There are some studies that solve CSSP in a polynomial time complexity w.r.t. the size of the original dataset. A simple and efficient selection algorithm with a linear complexity order, referred to as spectrum pursuit (SP), is proposed that pursuits spectral components of the dataset using available sample points. The proposed non-greedy algorithm aims to iteratively find K data samples whose span is close to that of the first K spectral components of entire data. SP has no parameter to be fine tuned and this desirable property makes it problem-independent. The simplicity of SP enables us to extend the underlying linear model to more complex models such as nonlinear manifolds and graph-based models. The nonlinear extension of SP is introduced as kernel-SP (KSP). The superiority of the proposed algorithms is demonstrated in a wide range of applications.

Recovering low-rank and sparse components from missing observations is an essential problem in various fields. In this paper, we have proposed a method to address the missing low-rank and sparse decomposition problem. We have used the smoothed nuclear norm and the L1norm to impose the low-rankness and sparsity constraints on the components, respectively. Furthermore, we have suggested a linear modeling for the corrupted observations. The problem has been solved with the aid of alternating minimization. Moreover, some simplifications have been applied to the relations to reduce the computational complexity, which makes the algorithm suitable for large-scale problems. To evaluate the proposed method, different simulation scenarios have been devised. The superiority of the suggested scheme over its counterparts has been confirmed on both the recovery accuracy and the convergence speed in various applications.

In this paper, we introduce a novel and robust approach to quantized matrix completion. First, we propose a rank minimization problem with constraints induced by quantization bounds. Next, we form an unconstrained optimization problem by regularizing the rank function with Huber loss. Huber loss is leveraged to control the violation from quantization bounds due to two properties: first, it is differentiable; and second, it is less sensitive to outliers than the quadratic loss. A smooth rank approximation is utilized to endorse lower rank on the genuine data matrix. Thus, an unconstrained optimization problem with differentiable objective function is obtained allowing us to advantage from gradient descent technique. Novel and firm theoretical analysis of the problem model and convergence of our algorithm to the global solution are provided. Another contribution of this letter is that our method does not require projections or initial rank estimation, unlike the state-of-the-art. In the Numerical Experiments section, the noticeable outperformance of our proposed method in learning accuracy and computational complexity compared to those of the state-of-the-art literature methods is illustrated as the main contribution.

Adaptive thresholding methods have proved to yield a high signal‐to‐noise ratio (SNR) and fast convergence in sparse signal recovery. The robustness of a class of iterative sparse recovery algorithms, such as the iterative method with adaptive thresholding, has been found to outperform the state‐of‐art methods in respect of reconstruction quality, convergence speed, and sensitivity to noise. In this study, the authors introduce a new method for compressed sensing, using the sensing matrix and measurements. In our method, they iteratively threshold the signal and project the thresholded signal onto the translated null space of the sensing matrix. The threshold level is assigned adaptively. The results of the simulations reveal that the authors’ proposed method outperforms other methods in the signal reconstruction (in terms of the SNR). This performance advantage is noticeable when the number of available measurements approaches twice the sparsity number.