Alireza Khayatian

Iman Hosseini, Alireza Khayatian, Paknoush Karimaghaee et al.

This paper proposes a novel kind of Unknown Input Observer (UIO) called Reset Unknown Input Observer (R-UIO) for state estimation of linear systems in the presence of disturbance using Linear Matrix Inequality (LMI) techniques. In R-UIO, the states of the observer are reset to the after-reset value based on an appropriate reset law in order to decrease the $L_2$ norm and settling time of estimation error. It is shown that the application of the reset theory to the UIOs in the LTI framework can significantly improve the transient response of the observer. Moreover, the devised approach can be applied to both SISO and MIMO systems. Furthermore, the stability and convergence analysis of the devised R-UIO is addressed. Finally, the efficiency of the proposed method is demonstrated by simulation results.

Alireza Khayatian, Anil Vullikanti, Aritra Konar

Many graph datasets involve sensitive network data, motivating the need for privacy-preserving graph mining. The Densest-$k$-subgraph (D$k$S) problem is a key primitive in graph mining that aims to extract a subset of $k$ vertices with the maximum internal connectivity. Although non-private algorithms are known for D$k$S, this paper is the first to design algorithms that offer formal differential privacy (DP) guarantees for the problem. We base our general approach on using the principal component (PC) of the graph adjacency matrix to output a subset of $k$ vertices under edge DP. For this task, we first consider output perturbation, which traditionally offer good scalability, but at the expense of utility. Our tight on the local sensitivity indicate a big gap with the global sensitivity, motivating the use of instance specific sensitive methods for private PC. Next, we derive a tight bound on the smooth sensitivity and show that it can be close to the global sensitivity. This leads us to consider the Propose-Test-Release (PTR) framework for private PC. Although computationally expensive in general, we design a novel approach for implementing PTR in the same time as computation of a non-private PC, while offering good utility for \DkS{}. Additionally, we also consider the iterative private power method (PPM) for private PC, albeit it is significantly slower than PTR on large networks. We run our methods on diverse real-world networks, with the largest having 3 million vertices, and show good privacy-utility trade-offs. Although PTR requires a slightly larger privacy budget, on average, it achieves a 180-fold improvement in runtime over PPM.