We consider the task of robust non-linear estimation in the presence of both bounded noise and outliers. Assuming that the unknown non-linear function belongs to a Reproducing Kernel Hilbert Space (RKHS), our goal is to accurately estimate the coefficients of the kernel regression matrix. Due to the existence of outliers, common techniques such as the Kernel Ridge Regression (KRR), or the Support Vector Regression (SVR) turn out to be inadequate. Instead, we employ sparse modeling arguments to model and estimate the outliers, adopting a greedy approach. In particular, the proposed robust scheme, i.e., Kernel Greedy Algorithm for Robust Denoising (KGARD), is a modification of the classical Orthogonal Matching Pursuit (OMP) algorithm. In a nutshell, the proposed scheme alternates between a KRR task and an OMP-like selection step. Convergence properties as well as theoretical results concerning the identification of the outliers are provided. Moreover, KGARD is compared against other cutting edge methods (using toy examples) to demonstrate its performance and verify the aforementioned theoretical results. Finally, the proposed robust estimation framework is applied to the task of image denoising, showing that it can enhance the denoising process significantly, when outliers are present.
We present a model of interacting multiple choices of opinions. At each step of the process, a listener is persuaded by his/her neighbour, the lobbyist, to modify his/her opinion on two different choices of event. Whether or not the listener will be convinced by the lobbyist depends on the difference between his/her opinion with that of the lobbyist, and with that of the revealed social opinion (the social pressure). If the listener is convinced, he/she will modify his/her opinion and update his/her revealed preference, and proceed to persuade his/her next neighbour. If the listener is not convinced by the lobbyist, he/she will retain his/her revealed preference, and try to persuade the lobbyist to change his/her opinion. In this case, the direction of opinion propagation is reversed. A consensus is reached when all the revealed preference is the same. Our numerical results show that consensus can always be attained in this model. However, the time needed to achieve consensus, or the so-called convergence time, is longer if the listener is more concerned with the public opinion, or is less likely to be influenced by the lobbyist.
In this paper we investigate the computational complexity of motivating time-inconsistent agents to complete long term projects. We resort to an elegant graph-theoretic model, introduced by Kleinberg and Oren, which consists of a task graph $G$ with $n$ vertices, including a source $s$ and target $t$, and an agent that incrementally constructs a path from $s$ to $t$ in order to collect rewards. The twist is that the agent is present-biased and discounts future costs and rewards by a factor $\beta\in [0,1]$. Our design objective is to ensure that the agent reaches $t$ i.e.\ completes the project, for as little reward as possible. Such graphs are called motivating. We consider two strategies. First, we place a single reward $r$ at $t$ and try to guide the agent by removing edges from $G$. We prove that deciding the existence of such motivating subgraphs is NP-complete if $r$ is fixed. More importantly, we generalize our reduction to a hardness of approximation result for computing the minimum $r$ that admits a motivating subgraph. In particular, we show that no polynomial-time approximation to within a ratio of $\sqrt{n}/4$ or less is possible, unless ${\rm P}={\rm NP}$. Furthermore, we develop a $(1+\sqrt{n})$-approximation algorithm and thus settle the approximability of computing motivating subgraphs. Secondly, we study motivating reward configurations, where non-negative rewards $r(v)$ may be placed on arbitrary vertices $v$ of $G$. The agent only receives the rewards of visited vertices. Again we give an NP-completeness result for deciding the existence of a motivating reward configuration within a fixed budget $b$. This result even holds if $b=0$, which in turn implies that no efficient approximation of a minimum $b$ within a ration grater or equal to $1$ is possible, unless ${\rm P}={\rm NP}$.