nonlinear controller is designed to synchronize each joint angle to a
corresponding reference trajectory. The absolute body orientation then
corresponds to the remaining (zero) dynamics of the controlled system.
Periodic walking gaits can thus be reduced to the limit cycle of these hybrid
dynamics, and the solution is efficiently found via numerical optimization.
The optimization objective is to minimize the energy consumption of locomotion
while optimizing the gait parameters.

Since four actuators are available in the non-instantaneous double support
phase which has three degrees of freedom, the model in the double support
phase is overactuated. We suggest three different control concepts in order to
utilize the overactuation to formulate different control tasks. The first
controller uses two independent virtual inputs that are projected onto the
four physical actuators to artificially create an underactuated double support
phase. The second controller uses the projection of three virtual inputs and
adds a new control objective to actively stabilize the limit cycle during the
double support phase, aiming on improving the gait stability. The last one
uses the physical actuators without virtual inputs and considers the
stabilization of the limit cycle and the collinearity of the contact forces on
the stance feet.

According to the optimization at different average walking speeds, the
controller with the underactuated double support phase achieves the highest
efficiency. The other control concepts have, however, better stability
properties. Since a point foot is modelled at the lower end of the leg, the
robot is not able to utilize its passive dynamics while walking. Humans have
actuated ankle joints and extended feet that roll over the ground and are thus
capable of creating more efficient gaits with a non-instantaneous double
support phase.

In future works, we are going to validate the control design on a real robot
prototype and measure the energy consumption. Also, instead of enforcing the
collinearity of the contact forces, other control tasks can be investigated in
the control design with overactuation, e. g. to improve the stability in the
frontal plane orthogonal to the walking direction, since the robot prototype
walks in a three dimensional space. Furthermore, the extended control concept
could be also applied for bipedal walking robots that have actuated feet
models with more degrees of freedom.

##  Appendix A Geometry in the Double Support Phase

The holonomic constraint
$\mathbf{q}_{\mathrm{dd}}=\hat{\mathbf{\Omega}}(\hat{\mathbf{q}}_{\mathrm{d}})$
in section 2.3 follows from Figure 13.

Figure 13: Geometric parameters of the closed kinematic chain formulated by
two stance legs during the continuous double support phase

The vector $\mathbf{r}_{HC_{1}}$ from hip to foot 1 is expressed using thigh
$\ell_{\mathrm{t}}$ and shank $\ell_{\mathrm{s}}$ as

$\mathbf{r}_{HC_{1}}=r_{HC_{1},x}\vec{e}_{x}+r_{HC_{1},z}\vec{e}_{z}\text{~{},}\\\
$ (118)

with

$\displaystyle r_{HC_{1},x}$
$\displaystyle=\ell_{\mathrm{t}}\sin\left(\theta_{\mathrm{HAT}}+\theta_{\mathrm{H}1}\right)+\ell_{\mathrm{s}}\sin\left(\theta_{\mathrm{HAT}}+\theta_{\mathrm{H}1}+\theta_{\mathrm{K}1}\right)\text{~{},}$
(119) $\displaystyle r_{HC_{1},z}$
$\displaystyle=\ell_{\mathrm{t}}\cos\left(\theta_{\mathrm{HAT}}+\theta_{\mathrm{H}1}\right)+\ell_{\mathrm{s}}\cos\left(\theta_{\mathrm{HAT}}+\theta_{\mathrm{H}1}+\theta_{\mathrm{K}1}\right)\text{~{}.}$

With the given step length $\ell_{\mathrm{step}}$,

$\displaystyle x_{H}$
$\displaystyle=r_{HC_{1},x}-\ell_{\mathrm{step}}\text{~{},}$ (120)
$\displaystyle z_{H}$ $\displaystyle=r_{HC_{1},z}\text{~{}.}$

Thus the length of vector $\mathbf{r}_{HC_{2}}$ is

$|\mathbf{r}_{HC_{2}}|=\sqrt{x_{H}^{2}+z_{H}^{2}}\text{~{}.}$ (121)

The law of cosines is applied to the triangle in leg 2 yielding

$|\mathbf{r}_{HC_{2}}|^{2}=\ell_{\mathrm{t}}^{2}+\ell_{\mathrm{s}}^{2}-2\ell_{\mathrm{t}}\ell_{\mathrm{s}}\cos(\beta_{2})\text{~{}.}$
(122)

Due to equal segment lengths $\ell_{\mathrm{t}}=\ell_{\mathrm{s}}$,

$\displaystyle\beta_{2}$
$\displaystyle=\arccos\left(1-\frac{|\mathbf{r}_{HC_{2}}|^{2}}{2\cdot\ell_{\mathrm{t}}^{2}}\right)\text{~{},}$
(123) $\displaystyle\gamma_{2}$
$\displaystyle=\alpha_{2}=\frac{\pi-\beta_{2}}{2}\text{~{}.}$

Therefore,

$\hat{\mathbf{\Omega}}(\hat{\mathbf{q}}_{\mathrm{d}})=\begin{bmatrix}\theta_{\mathrm{H}2}\\\
\theta_{\mathrm{K}2}\end{bmatrix}=\begin{bmatrix}\pi+\arctan\left(\frac{x_{H}}{z_{H}}\right)-\gamma_{2}-\theta_{\mathrm{HAT}}\\\
2\cdot\gamma_{2}\end{bmatrix}\text{~{}.}$ (124)

Author Contributions Yinnan Luo, Ulrich J. Römer and Alexander Dyck
contributed to the conception, method and analysis of the work. Yinnan Luo
implemented and evaluated the simulation. Yinnan Luo wrote the first draft of
the article. Ulrich J. Römer revised and improved the first draft. All authors
read and approved the final article.

Financial Support This work is supported by the German Research Foundation
(DFG), (grant FI 1761/4-1 $|$ ZE 714/16-1).

Conflicts of Interest The authors declare no conflicts of interest exist.

Ethical Approval Not applicable.

## References

  * [1] K. Yamamoto, T. Kamioka, and T. Sugihara. “Survey on model-based biped motion control for humanoid robots,” Advanced Robotics, 34(21-22), 1353–1369 (2020).
  * [2] J. Reher, and A.D. Ames. “Dynamic Walking: Toward Agile and Efficient Bipedal Robots,” Annual Review of Control, Robotics, and Autonomous Systems, 4, 535–572 (2021).
  * [3] Y. Hurmuzlu, F. GéNot, and B. Brogliato. “Modeling, stability and control of biped robots-a general framework,” Automatica, 40(10), 1647–-1664 (2004).
  * [4] S. Gupta, and A. Kumar. “A brief review of dynamics and control of underactuated biped robots,” Advanced Robotics, 31(12), 607–623 (2017).
  * [5] T. Stöckel, R. Jacksteit, M. Behrens, R. Skripitz, R. Bader, and A. Mau-Moeller. “The mental representation of the human gait in young and older adults,” Frontiers in psychology, 6, 943 (2015).
  * [6] M. van Mierlo, M. Vlutters, E.H.F. van Asseldonk and H. van der Kooij. “Centre of pressure modulations in double support effectively counteract anteroposterior perturbations during gait,” Journal of Biomechanics, 126, 110637 (2021).
  * [7] A.D. Kuo, J.M. Donelan, A. Ruina. “Energetic Consequences of Walking Like an Inverted Pendulum: Step-to-Step Transitions,” Exercise and Sport Sciences Reviews, 33(2), 88–97 (2005).
  * [8] J. M. Donelan, R. Kram, and A.D. Kuo. “Simultaneous positive and negative external mechanical work in human walking,” Journal of biomechanics, 35(1), 117-–124 (2002).
  * [9] H. Tran Thien, C. Van Kien, and H.P.H. Anh. “Optimized stable gait planning of biped robot using multi-objective evolutionary JAYA algorithm,” International Journal of Advanced Robotic Systems, 17(6), 1729881420976344 (2020).
  * [10] H.-o. Lim, and A. Takanishi. “Biped walking robots created at Waseda University: WL and WABIAN family,” Phil. Trans. R. Soc. A, 365(1850), 49–64 (2006).
  * [11] S. Ito, S. Amano, S. Minoru, and P. Kulvanit. “A ZMP Feedback Control for Biped Balance and its Application to In-Place Lateral Stepping Motion,” Journal of Computers, 3(8), 23–31 (2008).
  * [12] R. Rajendra, and D. Pratihar. “Analysis of double support phase of biped robot and multi-objective optimization using genetic algorithm and particle swarm optimization algorithm,” Sadhana 40(2), 549–575 (2015).
  * [13] T. Li, Z. Yu, J. Chen, Y. Liu, M. Zheng, L. Meng, G. Ma, W. Zhang, W. Zhang, and Q. Huang, “Stability control for biped walking based on phase modification during double support period,” 2014 IEEE International Conference on Robotics and Biomimetics (ROBIO 2014), 1290–1295 (2014).
  * [14] H. Dai, A. Valenzuela, and R. Tedrake, “Whole-body motion planning with centroidal dynamics and full kinematics,” in 2014 IEEE-RAS International Conference on Humanoid Robots, 295–-302 (2014).
  * [15] S. Kuindersma, R. Deits, M. Fallon, A. Valenzuela, H. Dai, F. Permenter, T. Koolen, P. Marion, and R. Tedrake, “Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot,” Autonomous Robots, 40(3), 429–-455 (2016).
  * [16] H. Hirukawa, S. Hattori, K. Harada, S. Kajita, K. Kaneko, F. Kanehiro, K. Fujiwara, and M. Morisawa, “A universal stability criterion of the foot contact of legged robots - adios ZMP,” in Proceedings 2006 IEEE International Conference on Robotics and Automation, 1976–-1983 (2006).
  * [17] J. Nocedal and S. Wright, Numerical Optimization (Springer, New York, 2006).
  * [18] J.T. Betts, Practical Methods for Optimal Control and Estimation Using Nonlinear Programming (Society for Industrial and Applied Mathematics, Philadelphia, 2010).
  * [19] M. DeDonato, V. Dimitrov, R. Du, R. Giovacchini, K. Knoedler, X. Long, F. Polido, M. A. Gennert, T. Padır, S. Feng, H. Moriguchi, E. Whitman, X. Xinjilefu, and C. G. Atkeson, “Human-in-the-loop Control of a Humanoid Robot for Disaster Response: A Report from the DARPA Robotics Challenge Trials,” Journal of Field Robotics, 32(2), 275–-292 (2015).
  * [20] S. Collins, A. Ruina, R. Tedrake, and M. Wisse. “Efficient bipedal robots based on passive-dynamic walkers,” Science, 307(5712), 1082–-1085 (2005).
  * [21] T. McGeer. “Passive Dynamic Walking,” The International Journal of Robotics Research, 9(2), 62-–82 (1990).
  * [22] E.R. Westervelt, J.W. Grizzle, and D. Koditschek, “Hybrid Zero Dynamics of Planar Biped Walkers,” IEEE Transactions on Automatic Control 48(1), 42–-56 (2003).
  * [23] C. Chevallereau, G. Abba, Y. Aoustin, F. Plestan, E.R. Westervelt, C. Canudas-De-Wit, and J.W. Grizzle, “RABBIT: a testbed for advanced control theory,” IEEE Control Systems Magazine 23(5), 57-–79 (2003).
  * [24] A.E. Martin, D.C. Post, and J.P. Schmiedeler, “Design and experimental implementation of a hybrid zero dynamics-based controller for planar bipeds with curved feet,” The International Journal of Robotics Research 33(7), 988–-1005 (2014).
  * [25] C. Chevallereau, J.W. Grizzle, and C.-L. Shih, “Asymptotically Stable Walking of a Five-Link Underactuated 3-D Bipedal Robot,” IEEE Transactions on Robotics, 25(1), 37–-50 (2009).
  * [26] J.W. Grizzle, C. Chevallereau, R.W. Sinnet, and A.D. Ames, “Models, feedback control, and open problems of 3D bipedal robotic walking,” Automatica, 50(8), 1955–-1988 (2014).
  * [27] A.D. Ames, “Human-Inspired Control of Bipedal Walking Robots,” IEEE Transactions on Automatic Control, 59(5), 1115–-1130 (2014).
  * [28] F. Bauer, U.J. Römer, A. Fidlin, and W. Seemann, “Optimization of energy efficiency of walking bipedal robots by use of elastic couplings in the form of mechanical springs,” Nonlinear Dynamics 83(3), 1275–-1301 (2016).
  * [29] F. Bauer, U.J. Römer, A. Fidlin, and W. Seemann, “Optimal elastic coupling in form of one mechanical spring to improve energy efficiency of walking bipedal robots,” Multibody System Dynamics 38, 227–-262 (2016).
  * [30] U.J. Römer, C. Kuhs, M.J. Krause, and A. Fidlin, “Simultaneous optimization of gait and design parameters for bipedal robots,” 2016 IEEE International Conference on Robotics and Automation (ICRA), 1374–1381 (2016).
  * [31] K.A. Hamed, N. Sadati, W.A. Gruver, and G.A. Dumont, “Stabilization of Periodic Orbits for Planar Walking With Noninstantaneous Double-Support Phase”, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 42(3), 685–706 (2012).
  * [32] M. Scheint, M. Sobotka and M. Buss, “Virtual holonomic constraint approach for planar bipedal walking robots extended to double support,” Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, 8180–8185 (2009).
  * [33] B.R. Umberger and P.E. Martin, “Mechanical power and efficiency of level walking with different stride rates,” Journal of Experimental Biology, 210(18), 3255–-3265 (2007).
  * [34] J.J. Eng and D.A. Winter. “Kinetic analysis of the lower limbs during walking: what information can be gained from a three-dimensional model?,” Journal of biomechanics, 28(6), 753–-758 (1995).
  * [35] E.R. Westervelt, G. Buche, and J.W. Grizzle, “Experimental Validation of a Framework for the Design of Controllers that Induce Stable Walking in Planar Bipeds,” The International Journal of Robotics Research, 23(6), 559–582 (2004).
  * [36] E.R. Westervelt, J.W. Grizzle, C. Chevallereau, J.H. Choi, and B. Morris, Feedback Control of Dynamic Bipedal Robot Locomotion (CRC Press, Boca Raton, 2013).
  * [37] G. H. Golub, and C. F. van Loan, Matrix Computations (JHU Press, Baltimore and London, 2013).
  * [38] J. T. Betts, “Survey of Numerical Methods for Trajectory Optimization,” Journal of Guidance, Control, and Dynamics, 21(2), 193–-207 (1998).
  * [39] M. Posa, C. Cantu, and R. Tedrake, “A direct method for trajectory optimization of rigid bodies through contact,” The International Journal of Robotics Research, 33(1), 69-–81 (2014).
  * [40] A. Hereid, C. M. Hubicki, E.A. Cousineau, and A.D. Ames, “Dynamic Humanoid Locomotion: A Scalable Formulation for HZD Gait Optimization,” IEEE Transactions on Robotics, 34(2), 370–-387 (2018).
  * [41] F. Bauer, Optimierung der Energieeffizienz zweibeiniger Roboter durch elastische Kopplungen (Dissertation) (KIT Scientific Publishing, Karlsruhe, 2014).
  * [42] Y. Luo, U.J. Römer, L. Zentner and A. Fidlin. “Improving Energy Efficiency of a Bipedal Walker with Optimized Nonlinear Elastic Coupling,” Advances in Nonlinear Dynamics. NODYCON Conference Proceedings Series, 253–262 (2022).


# Privacy-Preserving Near Neighbor Search via
Sparse Coding with Ambiguation

Behrooz Razeghi1, Sohrab Ferdowsi2, Dimche Kostadinov3, Flavio. P. Calmon4,
Slava Voloshynovskiy1  1University of Geneva  2HES-SO Geneva  3University of
Zurich  4Harvard University

###### Abstract

In this paper, we propose a framework for privacy-preserving approximate near
neighbor search via stochastic sparsifying encoding. The core of the framework
relies on sparse coding with ambiguation (SCA) mechanism that introduces the
notion of inherent shared secrecy based on the support intersection of sparse
codes. This approach is ‘fairness-aware’, in the sense that any point in the
neighborhood has an equiprobable chance to be chosen. Our approach can be
applied to raw data, latent representation of autoencoders, and aggregated
local descriptors. The proposed method is tested on both synthetic i.i.d data
and real large-scale image databases.

##  I Introduction

Many modern signal processing, machine learning and data mining applications,
such as biometric authentication/identification, pattern recognition, speech
processing and recommender systems, require near neighbor search of a query
with respect to a given dataset, and a distance measure. Many search services
are outsourced to third parties (service providers) who possess powerful
storage, communications and computing facilities. The major challenge is to
satisfy privacy constraints of the owner’s data and the clients’ interests,
while still being capable of performing the fast search service in multi-
billion entry datasets.

Let $\left(\mathcal{S},d_{\mathcal{S}}\right)$ be a metric space. Given a set
$\mathcal{X}\subseteq\mathcal{S}$ of $M$ points, a parameter $r$, and a query
point $\mathbf{y}\in\mathcal{S}$, the goal of the exact near neighbor (NN)
problem is to find a point $\mathbf{x}\in\mathcal{X}$ such that
$d_{\mathcal{S}}\left(\mathbf{x},\mathbf{y}\right)\leq r$, if such a point
exists. In the approximate variant of this problem (ANN), given $c>1$, the
problem is relaxed to find a point $x\in\mathcal{X}$ such that
$d_{\mathcal{S}}\left(\mathbf{x},\mathbf{y}\right)\leq cr$. Theses problems
can be generalized to $k$-NN and $k$-ANN setting. In this context, we assume
$\mathcal{S}$ to be the $N$-dimensional Euclidean space, i.e.,
$\mathcal{S}=\mathbb{R}^{N}$, and the distance given by an $\ell_{2}$-norm,
$d_{\mathcal{S}}\left(\mathbf{x},\mathbf{y}\right)=\|\mathbf{x}-\mathbf{y}\|_{2}$.
The NN search based on naïve solution, i.e., the linear scan, is the
bottleneck of the system in large scale high-dimensional data sets [1].
Alternatively, approximate near neigbor (ANN) search, is more efficient in
terms of query time and space complexity [2, 3, 4]. Perhaps the most popular
solution to ANN problem is via hashing, where the aim is to transform the data
points to a lower dimensional space, then perform similarity search in the
lower dimensional representation. The two main research directions are (1)
Locality Sensitive Hashing (LSH): indexing points using a hash table with the
property that similar (closer) data points have a higher probability of
collision than dissimilar (far) points [1, 2, 3, 4, 5, 6, 7]; (2) learning to
hash: performing NN similarity search in a low dimensional space with a lower
search complexity [8, 9, 10, 1, 11]. The objective in the latter methodology
is to preserve semantic or distance similarity between the original space and
transformed space. Subsequent research showed that quantization-based
solutions are preferred in terms of query time, space cost and search accuracy
[1].

Figure 1: The general block diagram of our framework.

Concretely, this work brings the following contributions: (1) We consider the
methodology of learning to hash for privacy-preserving proximity search which
entails minimum information loss for authorized users. The authorized parties
can purify the ambiguation noise using the shared secrecy based on the support
intersection of sparse codes [12].
(2) We adopt a notion of fairness addressed in [7], but in a privacy-
preserving setup. Our notion of fairness differs from machine learning
algorithms where the goal is to handle the bias introduced at the training
phase. We consider the bias in the stored data and querying response. By doing
this, any point in the neigborhood has an equal chance to be chosen. Moreover,
in some cases, it may suffice to return any of the points in the near
neighborhood, rather than the computationally expensive nearest one. The
equiprobable nearby scheme can also be utilized in privacy protection
mechanisms. That is, instead of reporting the nearest-neighbor, which leaks
more information, the service provider just sends back a random or a typical
data point close to the query point.

In comparison to [13, 14], our work has the following fundamental differences:
a) In [13, 14, 15, 16], they utilized a dimensionality reduction transform
with random entries, while our sparsifying transform may keep, extend, or
reduce the dimension of the original data. Moreover, our transform is learned
using the sparsifying transform problem to ensure an optimal sparse
representational that is information preserving in general, whereas the
transform in [13, 14, 15] might preserve the distances only under certain
conditions of the Johnson-Lindenstrauss Lemma. b) In [13, 14, 16], the codes
are dense and binary, whereas in our method the codes are sparse (and possibly
ternary), which form a basis of our ambiguation framework. Last but not the
least, the embedding based on universal quantization scheme [13] has
information leakage in terms of clustering, i.e., the curious server still can
perform clustering on data points. Moreover, we impose no restrictions on the
input data, i.e., we assume that as an input we might have raw data, extracted
features using any known hand crafted methods, aggregated local descriptors
based on BoW, FV, VLAD [17, 18, 19], etc., or from the last layers of deep
nets [20], or the latent space of auto-encoders [21]. We apply our model on
the latent representation of a designed network in [12].

Throughout this paper, superscript $(\cdot)^{T}$ stands for the transpose.
Vectors and matrices are denoted by boldface lower-case ($\mathbf{x}$) and
upper-case ($\mathbf{X}$) letters, respectively. We consider the same notation
for a random vector $\mathbf{x}$ and its realization. The difference should be
clear from the context. $x_{i}$ denotes the $i$-th entry of vector
$\mathbf{x}$. For a matrix $\mathbf{X}$, $\mathbf{x}{\left(j\right)}$ denotes
the $j$-th column of $\mathbf{X}$. We use the notation $\left[N\right]$ for
the set $\\{1,2,...,N\\}$.

##  II Preliminaries

###  II-A Problem Setup

Consider a three-party data release scenario involving (a) a data owner, (b)
data users, and (c) a service provider (server). The data owner possesses
database $\mathbf{X}\\!=\\!\left[\mathbf{x}(1),\cdots,\mathbf{x}(M)\right]$
consisting of $M$ data points $\mathbf{x}(m)\\!\in\\!\mathbb{R}^{N}$,
$m\in\left[M\right]$. The database is used to offer some utility for the
authorized data users. The data users seek some utility from the data owner
based on their query $\mathbf{y}$. The server provides a pre-determined
service to the data users on behalf of the data owner. We assume that both the
server and data users are honest-but-curious, which we consider them as an
adversary. The service provider may try to infer some information about the
original data collection $\mathcal{X}$ from the disclosed public storage
and/or the querying data sent to the server. For instance, the server may
estimate the original data from the disclosed representations and query, or
may establish links between the closet entries in database. The data users may
try to infer some information about the public representations and/or the
original data via multiple varied queries to guess the data manifold by
inspecting the returned responses. A general diagram of our framework is
depicted in Fig. 1.

Therefore, we study the problem of disclosing database $\mathbf{X}$ to a
third-party (public storage) in order to drive some utility, in terms of near
neighbor search, for the authorized data users based on the public
representations while, at the same time, protect the privacy of the data owner
(against the honest-but-curious server and data users) and data users (against
the honest-but-curious server).

###  II-B Fair Near Neighbor

Let $\left(\mathcal{S},d_{\mathcal{S}}\right)$ be a metric space and let
$\mathcal{X}\subseteq\mathcal{S}$ be a set of $M$ data points. Let
$B_{\mathcal{S}}\left(\mathbf{c},r\right)=\\{\mathbf{x}\in\mathcal{S}\mid
d_{\mathcal{S}}\left(\mathbf{c},\mathbf{x}\right)\leq r\\}$ be the closed ball
of radius $r>0$ around a point $\mathbf{c}\in\mathcal{S}$. Let
$N\left(\mathbf{c},r\right)=B_{\mathcal{S}}\left(\mathbf{c},r\right)\cap\mathcal{X}$
be the $r$-neighborhood of $\mathbf{c}$ in $\mathcal{X}$, with the size
$|N\left(\mathbf{c},r\right)|$.

######  Definition 1.

Fair Near Neighbor (FNN) [7]. Given a data set
$\mathcal{X}\subseteq\mathcal{S}$ of $M$ data points, a parameter $r>0$, and
query point $\mathbf{y}$, the goal is to find a data point $\mathbf{x}\in
N\left(\mathbf{y},r\right)$ with probability $\mu$, where
$1/\\!\left(|N\left(\mathbf{y},r\right)|(1+\epsilon)\right)\\!\leq\\!\mu\\!\leq\\!(1\\!+\epsilon)/|N\left(\mathbf{y},r\right)\\!|$,
i.e., $\mu$ is an approximately uniform probability distribution.

Figure 2: Visualization of desired property of mapping scheme in privacy-
preserving near neighbor search setup.

###  II-C Fair Privacy-Preserved Approximate Near Neigbor

Let $\left(\mathcal{T},d_{\mathcal{T}}\right)$ be a metric space where
$d_{\mathcal{T}}\left(\mathbf{a},\mathbf{b}\right),\forall\mathbf{a},\mathbf{b}\in\mathcal{T}$
is defined on $\mathrm{supp}(\mathbf{a})=\\{l\in[L]:a_{l}\neq 0\\}$. Let
$\mathcal{P}\subseteq\mathcal{T}$ be a set of $M$ data points. Let
$B_{\mathcal{T}}\left(g(\mathbf{y}),r\right)=\\{f(\mathbf{x})\in\mathcal{T}\mid
d_{\mathcal{T}}\left(g(\mathbf{y}),f(\mathbf{x})\right)\leq r\\}$. Now, we
define the Fair Privacy-preserved Approximate Near Neighbor method as follows:

######  Definition 2.

Fair Privacy-preserved Approximate Near-Neighbor (FPANN). Given a data set
$\mathcal{X}\subseteq\mathcal{S}$ of $M$ data points, a parameter $r>0$, the
goal is to design a randomized privacy-preserving data release mechanism
$f:\mathcal{X}\rightarrow\mathcal{P}$ and (randomized) query processing
$g:\mathcal{S}\rightarrow\mathcal{T}$ such that for a given authorized query
$\mathbf{y}$ one can report a point $f\left(\mathbf{x}\right)\in
N_{\mathcal{T}}\left(g(\mathbf{y}),r\right)$ with probability $\mu_{p}$, where
$N_{\mathcal{T}}\left(g(\mathbf{y}),r\right)=B_{\mathcal{T}}\left(g(\mathbf{y}),r\right)\cap\mathcal{P}$
be the approximate $r$-neighbor of $g(\mathbf{y})$ in $\mathcal{P}$, and
$1/\left(|N\left(g(\mathbf{y}),r\right)\\!|\,(1+\epsilon)\right)\leq\mu_{p}\leq(1+\epsilon)/|N\left(g(\mathbf{y}),r\right)\\!|$.

######  Definition 3.

$\left(\beta,\gamma\right)$-recoverable privacy mechanism. For
$0\leq\gamma\leq 1$ and given authorized query $\mathbf{y}^{\mathrm{auth}}$,
unauthorized query $\mathbf{y}^{\mathrm{unauth}}$ and $\beta>0$, a privacy-
preserving data release mechanism $f:\mathcal{X}\rightarrow\mathcal{P}$ is
$\left(\beta,\gamma\right)$-recoverable if:

$\displaystyle(i):\quad P_{e}^{\mathrm{auth}}\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\mathrm{Pr}\left[\mathbb{E}\left[d\left(\mathbf{x},\mathbf{\hat{x}}\right)\right]\leq\beta\mid
g\left(\mathbf{y}^{\mathrm{auth}}\right)\right]<\gamma,$
$\displaystyle(ii):P_{e}^{\mathrm{unauth}}\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\mathrm{Pr}\left[\mathbb{E}\left[d\left(\mathbf{x},\mathbf{\hat{x}}\right)\right]\leq\beta\mid
g\left(\mathbf{y}^{\mathrm{unauth}}\right)\right]\geq\gamma,$

where $g(\cdot)$ is the data user’s query function to service provider.

##  III Proposed Framework

###  III-A Framework Overview

Our framework is composed of the following steps:

1) Preparation at Owner Side: The owner generates the sparse codewords from
the data that s/he owns using the trained sparsifying transform. Next, he
shares the privacy-protected sparse codebook with the service provider
(server). Following Kerckchoffs’s Principle in cryptography, the data owner
makes the learned sparsifying transform publicly available.

2) Indexing at Server Side: The server indexes the received sparse codes in a
database.

3) Querying at Data User Side: The data user generates a sparse representation
from his query data using the shared transform. Then, the client sends a
function of his sparse representation to the server.

4) Near Neighbor Search at Server Side: Given the requested probe, the server
runs a near neighbor search to find the stored sparse codes that are most
similar (close) to the probe. Finally, based on the pre-determined service to
the data users, the server sends back an answer to the data user.

Next, we describe in more detail the fundamental elements of our mechanism.

###  III-B Sparse Data Representation

The goal of sparsification is to obtain an information-preserving sparse
representation of the original data. Our sparsifying transform consists of a
linear mapper followed by an element-wise nonlinearity. We consider a joint
learning problem to obtain the sparsifying transform
$\mathbf{W}\in\mathbb{R}^{L\times N}$ as well as the sparse codebook
$\mathbf{A}\in\mathbb{R}^{L\times M}$ that can be formulated as:

$\\!\\!\\!\big{(}\mathbf{\hat{W}},\\!\mathbf{\hat{A}}\big{)}\\!=\\!\mathrm{arg}\\!\mathop{\min}_{\left(\mathbf{W},\mathbf{A}\right)}\\!{\|\mathbf{W}\mathbf{X}\\!-\\!\mathbf{A}\|}_{F}^{2}\\!+\\!\beta_{1}\Omega_{1}\\!\left(\mathbf{W}\right)\\!+\\!\beta_{2}\Omega_{2}\\!\left(\mathbf{A}\right),$
(1)

where $\beta_{1}\geq 0$ and $\beta_{2}\geq 0$ are regularization parameters,
$\Omega_{1}\\!\left(\mathbf{W}\right)=(\frac{1}{\beta_{1,1}}\|{\bf
W}\|_{F}^{2}+\frac{1}{\beta_{1,2}}\|{\bf W}{\bf W}^{T}-{\bf
I}\|_{F}^{2}-\frac{1}{\beta_{1,3}}\log|\det{\bf W}^{T}{\bf W}|)$ penalizes the
information loss in order to avoid trivial solutions, and
$\Omega_{2}\\!\left(\mathbf{A}\right)$ is the sparsity constraint on the
compressed codebook $\mathbf{A}$ [22]. The term
${\|\mathbf{W}\mathbf{X}\\!-\\!\mathbf{A}\|}_{F}^{2}$ is a sparsification
error, which represents the deviation of the transformed data from the exact
sparse representation in the transformed domain 111We refer the reader to [23,
24, 25] for applications in group membership verification. Our algorithm for
solving (1) alternates between a $\ell_{0}$-“norm"-based sparse coding step,
and a non-convex transform update step [26]. Therefore, one can write the
closed-form formulation of the encoder as [26, 27]:

$\mathbf{a}(m)=\varphi\left(\mathbf{x}(m)\right)=\psi_{\lambda}\left(\mathbf{W}\mathbf{x}(m)\right),\forall
m\in\left[M\right],$ (2)

where
$\psi_{\lambda}\\!\left(\mathbf{f}\right)\\!=\\!\mathds{1}_{|f_{l}|\geq\lambda}{\mathbf{f}},\forall
l\\!\in\\!\left[L\right],\lambda\geq 0$ and $\mathbf{a}(m)$ is $S_{x}$-sparse,
i.e., $\|\mathbf{a}(m)\|\\!\approx\\!S_{x},\forall m\in\left[M\right]$. The
decoder (reconstruct mapper) $\mathbf{R}\in\mathbb{R}^{N\times L}$ can be
formulated as follows:

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathop{\min}_{\mathbf{R}}\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!{\|\mathbf{R}\mathbf{A}\\!-\\!\mathbf{X}\|}_{F}^{2}+\\!\beta_{R}{\|\mathbf{R}\\!-\\!{\left(\mathbf{W}^{T}\mathbf{W}\\!+\\!\beta\mathbf{I}\right)}^{\\!-1}\mathbf{W}^{T}\\!\|}_{F}^{2},$
$\displaystyle\mathrm{st:}\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!\mathbf{R}^{T}\mathbf{R}=\mathbf{I},$ (3)

where $\mathbf{A}\in\mathbb{R}^{L\times M}$ is sparse codebook,
$\mathbf{X}\in\mathbb{R}^{M\times N}$ is original data points and
$\mathbf{W}\in\mathbb{R}^{L\times N}$ is encoder transform. Since $\mathbf{R}$
has orthonormal columns, we have
${\|\mathbf{R}\\!\mathbf{A}\\!-\\!\mathbf{X}\|}_{F}^{2}\\!\\!\\!=\\!\\!\\!\\!\\!\\!\mathrm{tr}\\!\left[\mathbf{X}^{T}\mathbf{X}\\!-\\!2\mathbf{X}^{T}\mathbf{R}\mathbf{A}\\!+\\!\mathbf{A}^{T}\\!\mathbf{A}\right]\\!,{\|\mathbf{R}\\!-\\!\\!{\left(\mathbf{W}^{T}\mathbf{W}\\!\\!+\\!\beta\mathbf{I}\right)\\!}^{\\!-1}\mathbf{W}^{T}\|}_{F}^{2}\\!\\!\\!\\!=\\!\\!\\!\\!\mathrm{tr}\\!\left[\mathbf{I}-2\mathbf{C}^{T}\mathbf{R}+\mathbf{C}^{T}\mathbf{C}\right]$,
where
$\mathbf{C}={\left(\mathbf{W}^{T}\mathbf{W}+\beta\mathbf{I}\right)}^{-1}\mathbf{W}^{T}$.
Consequently (III-B) is equivalent to the problem of maximizing
$\mathrm{tr}\left[\mathbf{X}^{T}\mathbf{R}\mathbf{A}\right]+\beta_{R}\mathrm{tr}\left[\mathbf{C}^{T}\mathbf{R}\right]=\mathrm{tr}\left[\left(\mathbf{A}\mathbf{X}^{T}+\beta_{R}\mathbf{C}^{T}\right)\mathbf{R}\right]$.
Considering the Singular Value Decomposition
$\mathbf{A}\mathbf{X}^{T}+\beta_{R}\mathbf{C}^{T}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{T}$,
this formulation reduces to
$\mathrm{tr}\left[\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{T}\mathbf{R}\right]=\mathrm{tr}\left[\mathbf{\Sigma}\mathbf{Z}\right]=\sum_{i}z_{ii}\Sigma_{ii}\leq\sum_{i}\Sigma_{ii},$
where $\mathbf{Z}=\mathbf{V}^{T}\mathbf{R}\mathbf{U}$. Note that the last
inequality holds because $\mathbf{Z}$ is an orthonormal matrix, and
$\sum_{j}z_{ij}^{2}=1$, $z_{ii}\leq 1$. Therefore, the maximum can be achieved
if $\mathbf{Z}=\mathbf{I}$, i.e., closed form solution is
$\mathbf{R}=\mathbf{U}\mathbf{V}^{T}$, where
$\mathbf{A}\mathbf{X}^{T}+\beta_{R}\big{(}{\left(\mathbf{W}^{T}\mathbf{W}+\beta\mathbf{I}\right)}^{-1}\mathbf{W}^{T}\big{)}^{T}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{T}$.

###  III-C Ambiguation Mechanism

The idea of ambiguation is to add (pseudo) random noise to the orthogonal
complement, i.e., non-informative components of the sparse code. The
integration of ‘sparse lossy coding’ with ‘ambiguation’ introduces a
generalized randomization technique, namely Sparse Coding with Ambiguation
(SCA) [27]. The SCA provides an information-theoretically and computationally
private mechanism. The information-theoretical privacy guarantee originate
from the lossy compression induced at the sparsification stage, and the
computational privacy guarantee originate from ambiguation stage. The curious
server faces a combinatorial complexity budget requirement to guess the
informative components. The ambiguation noise is required to have the same
distribution as the sparse codes, to guarantee being indistinguishable from
its statistical properties. We refer the reader to [27] for more details. The
randomized privacy-preserving data release mechanism
$f:\mathcal{X}\rightarrow\mathcal{P}\subseteq\mathcal{T}$ can be formulated
as:

$\mathbf{p}(m)=f\\!\left(\mathbf{x}(m)\right)=\varphi\\!\left(\mathbf{x}(m)\right)\oplus\mathbf{n}_{\mathrm{supp}}^{p},\;\forall
m\in\left[M\right],$ (4)

where ${\|\mathbf{n}_{\mathrm{supp}}^{p}\|}_{0}\approx S_{p}$.

Given a query point $\mathbf{y}$, the (randomized) query release mechanism
$g:\mathcal{S}\rightarrow\mathcal{T}$ can be formulated as:

$\mathbf{q}=g\\!\left(\mathbf{y}\right)=\varphi\left(\mathbf{y}\right)\oplus\mathbf{n}_{\mathrm{supp}}^{q},$
(5)

where ${\|\mathbf{n}_{\mathrm{supp}}^{q}\|}_{0}\leq S_{q}$, $0\leq S_{q}\leq
S_{p}$. If $S_{q}=0$, the query is disclosed as in-the-clear sparse code
without ambiguation noise. Let us consider two hypotheses for near neighbor
search as follows. $\mathcal{H}_{1}$: The authorized query is related to one
of the $M$ data points in the database. For instance, it is a noisy version of
one data point. $\mathcal{H}_{0}$: The unauthorized query is not related to
any data point. For instance, it is synthetic query generated by an adversary.

###  III-D Near Neighbor Search

The near neighbor search is performed in latent space $\mathcal{T}$. Given a
data set $\mathcal{P}$ of $M$ embedded disclosed representations
$\\{\mathbf{p}(m)\\},m\in\left[M\right]$, a parameter $r$, and embedded query
point $\mathbf{q}$, the service provider performs approximate near neighbor
search and report a point randomly and uniformly from
$B_{\mathcal{T}}\left(\mathbf{q},r\right)\cap\mathcal{P}$.

##  IV Discussion

We now discuss various properties of our method. One desired property of an
embedding scheme in a privacy-preserving near neighbor search is to preserve
distance information only up to a specified radius, while quickly flattening
after this distance threshold. Therefore, from one hand, the information rate
is spent in encoding local distances, and from the other hand, the curious
server/data user cannot recover any distance information about signals that
are far apart. Fig. 2 visualizes this local isometric mapping, where
$d_{\mathcal{S}}\left(\cdot,\cdot\right)$ and
$d_{\mathcal{T}}\left(\cdot,\cdot\right)$ denote the distance measure in
original domain and transform domain, respectively.

Suppose
$\mathbf{x}\\!\sim\\!\mathcal{N}\\!\left(\bm{0},\sigma_{\mathbf{x}}\mathbf{I}_{N}\right)$
and $\mathbf{y}^{\mathrm{auth}}\\!=\\!\mathbf{x}+\mathbf{z}$, where
$\mathbf{z}\sim\mathcal{N}\\!\left(\bm{0},\sigma_{\mathbf{z}}\mathbf{I}_{N}\right)$,
and where $\mathbf{x}\in\mathbf{X}$. Fig.3(a) depicts the behaviour of our
embedding for two sparsity levels and compare them with linear embeddings
which preserve all distances equally. Let us define:

$\displaystyle P_{c}\\!$ $\displaystyle=$
$\displaystyle\\!\frac{1}{M.S_{x}}\sum\mathrm{Pr}\\{\mathrm{supp}\left(\varphi(\mathbf{x})\right)=\mathrm{supp}\left(\varphi(\mathbf{y})\right)\\},$
$\displaystyle P_{m}\\!$ $\displaystyle=$
$\displaystyle\\!\frac{1}{M.S_{x}}\sum\mathrm{Pr}\\{\mathrm{supp}\left(\varphi(\mathbf{x})\right)\neq\mathrm{supp}\left(\varphi(\mathbf{y})\right)\\}.$

Fig.3(b) illustrates the probability of correct support and missed support for
the learned linear map $\mathbf{W}_{1}$ (problem (1)) and
$\mathbf{W}_{2}=\mathbf{I}$. The learned transform outperforms in local
distances.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 3: a) local distance preserving; b) local robustness; (c) and (d):
Comparison of distortion-sparsity behavior for c) authorized and d)
unauthorized parties; (e) and (f) $R-$recall$@T$ curves for a subset of 10K
CelebA images of $3\times 128\times 128$.

|  | $S_{p}=0$ | $S_{x}=16$
---|---|---|---
|  | $S_{x}=1$ | $S_{x}=2$ | $S_{x}=4$ | $S_{x}=8$ | $S_{x}=16$ | $S_{p}=0$ | $S_{p}=8$ | $S_{p}=16$ | $S_{p}=24$ | $S_{p}=32$
MNIST | MSE | $0.7331$ | $0.6351$ | $0.5101$ | $0.3758$ | $0.2726$ | $0.2726$ | $0.4030$ | $0.4963$ | $0.5607$ | $0.6120$
SSIM | $0.5838$ | $0.6712$ | $0.7694$ | $0.8628$ | $0.9335$ | $0.9335$ | $0.8124$ | $0.7330$ | $0.6750$ | $0.6290$
F-MNIST | MSE | $0.5355$ | $0.4298$ | $0.3368$ | $0.2657$ | $0.2236$ | $0.2236$ | $0.2775$ | $0.3255$ | $0.3635$ | $0.4026$
SSIM | $0.4926$ | $0.5989$ | $0.6976$ | $0.7753$ | $0.8242$ | $0.8242$ | $0.7506$ | $0.6835$ | $0.6351$ | $0.5914$
CIFAR-10 | MSE | $0.3993$ | $0.3439$ | $0.2741$ | $0.2061$ | $0.1593$ | $0.1593$ | $0.2066$ | $0.2420$ | $0.2703$ | $0.2920$
SSIM | $0.4711$ | $0.5429$ | $0.6342$ | $0.7289$ | $0.8002$ | $0.8002$ | $0.7188$ | $0.6619$ | $0.6179$ | $0.5883$

TABLE I: Reconstruction quality vs sparsity and ambiguation levels.

###  IV-A Reconstruction Leakage

A potential threat is that the adversary may try to reconstruct the original
data points from the disclosed representations. To get insight into the SCA
model, we firstly provide the results on a synthetic database establish its
connection to classical Shannon rate-distortion theory. Next, we validate our
model on real image databases. For the sake of completeness, we also bring the
results provided in [11] on synthetic i.i.d data. Note that the sparsity level
$S_{x}$ controls the information encoding rate, or equivalently, the
distinguishability of data points in the transform domain. The ambiguation
level $S_{p}$ controls the imposed randomness to the informative data.

Fig. 3(c) and Fig. 3(d) illustrate and compare distortion-sparsity behavior at
authorized and unauthorized parties, respectively. Fig.3(c) depicts
reconstruction fidelity for four cases: 1) unquantized sparsifying encoding
(2), 2) Sparse Ternary Coding (STC) for independent and identically
distributed (i.i.d.) data [27], 3) STC for i.i.d. data which re-scaled in
original domain [11], and 4) STC for correlated data which are drawn from
AR(1) model with the parameter $\rho=0.5$. We used the same experimental
setting as [11]. Fig.3(d) shows the reconstruction leakage at a curious server
(or an adversary) who knows the encoder and its parameters, but has no
knowledge about the correct indices to purify the ambiguated representations.
The terminology ‘half ambiguation’ is defined as
$S_{p}\\!=\\!0.5(L\\!-\\!S_{x})$, and the terminology ‘full ambiguation’ is
defined as $S_{p}\\!=\\!L-\\!S_{x}$. Note that the information security
guarantee addressed in [13], required keeping the projection parameters
secretly.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 4: t-SNE visualizations from MNIST dataset on: a) original space, b)
transformed space with ambiguation, c) transformed space after purification,
d) reconstructed space without knowledge of support, e) reconstructed space
with knowledge of support; f) conceptual visualization of data clustering
leakage.

Table I provides a quantitative comparison on reconstructed images using
normalized MSE and SSIM (Structural Similarity Index) on MNIST [28], Fashion-
MNIST [29], and CIFAR-10 [30] databases, where we applied the proposed method
on latent representation of a designed convolutional autoencoder in [12],
setting $L=128$ and considering one code-map for MNIST and Fashion-MNIST
databases and four code-maps for CIFAR-10 database. Finally, note that based
on these results, our model follows the notion of
$\left(\beta,\gamma\right)$-recoverable privacy mechanism, which we defined in
Section II.

As a large-scale retrieval experiment, Figs. 3(e)-3(f) depict the recall
measure for the CelebA database. The ground-truth was the pixel domain
Euclidean distances and the latent code of the network in [12] is used to
measure the approximate distances.

###  IV-B Clustering Leakage

Another potential threat is that the adversary may establish links between the
closet disclosed representations. We now discuss database clustering leakage
under our model. Note that the proposed mechanism can apply to privacy-
preserving clustering applications where the goal is to perform clustering
without disclosing the original data. The significant benefit of our method is
that the authorized data users can purify the imposed ambiguation noise.
However, the adversary will face a combinatorial problem to guesses the
correct components.

Fig. 4 provides a qualitative visualization of clustering leakage on MNIST
database [28], for which t-distributed stochastic neighbor embedding (t-SNE)
[31] is used to project the underlying space to 2D. As illustrated, our model
prevent database clustering leakage. Denoting by $P_{\mathrm{intra}}$ and
$P_{\mathrm{inter}}$ as probability density functions of ‘intra-cluster’ and
‘inter-cluster’ of distances, respectively, Fig. 4(f), provides a conceptual
visualization of database clustering leakage, where
$D\left(P_{1}\|P_{2}\right)=\mathbb{E}_{P_{1}}[\log\frac{P_{1}}{P_{2}}]$.

##  V Conclusion

We present a computationally efficient, fairness-aware privacy-preserving
nearby search scheme that can be utilized in cloud-based applications. The key
insight behind our mechanism is that by approximating sparse representation of
data points and adding random noise to their orthogonal complement, we can
control privacy and utility trade-off in terms of dataset reconstruction and
dataset clustering. The authorized data users can purify the ambiguated public
representation thanks to the knowledge of correct support of the query.

## References

  * [1] Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al.,  “A survey on learning to hash,”  IEEE transactions on pattern analysis and machine intelligence, vol. 40, no. 4, pp. 769–790, 2017.
  * [2] Piotr Indyk and Rajeev Motwani,  “Approximate nearest neighbors: towards removing the curse of dimensionality,”  in Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998, pp. 604–613.
  * [3] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al.,  “Similarity search in high dimensions via hashing,”  in Vldb, 1999, vol. 99, pp. 518–529.
  * [4] Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang,  “Learning to hash for indexing big data—a survey,”  Proceedings of the IEEE, vol. 104, no. 1, pp. 34–57, 2015.
  * [5] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni,  “Locality-sensitive hashing scheme based on p-stable distributions,”  in Annual Symposium on Computational Geometry. ACM, 2004, pp. 253–262.
  * [6] Tobias Christiani,  “Fast locality-sensitive hashing frameworks for approximate near neighbor search,”  in Int. Conf. on Similarity Search and Applications. Springer, 2019, pp. 3–17.
  * [7] Sariel Har-Peled and Sepideh Mahabadi,  “Near neighbor: Who is the fairest of them all?,”  in Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 13176–13187.
  * [8] Ruslan Salakhutdinov and Geoffrey Hinton,  “Semantic hashing,”  International Journal of Approximate Reasoning, vol. 50, no. 7, pp. 969–978, 2009.
  * [9] Yair Weiss, Antonio Torralba, and Rob Fergus,  “Spectral hashing,”  in Advances in neural information processing systems, 2009, pp. 1753–1760.
  * [10] Sohrab Ferdowsi, Slava Voloshynovskiy, Dimche Kostadinov, and Taras Holotyak,  “Sparse ternary codes for similarity search have higher coding gain than dense binary codes,”  in IEEE Int. Symp. on Inf. Theory (ISIT), 2017.
  * [11] Behrooz Razeghi and Slava Voloshynovskiy,  “Privacy-preserving outsourced media search using secure sparse ternary codes,”  in IEEE Int. Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018, pp. 1–5.
  * [12] Sohrab Ferdowsi, Behrooz Razeghi, Taras Holotyak, Flavio P. Calmon, and Slava Voloshynovskiy,  “Privacy-preserving image sharing via sparsifying layers on convolutional groups,”  in IEEE Int. Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020.
  * [13] Petros Boufounos and Shantanu Rane,  “Secure binary embeddings for privacy preserving nearest neighbors,”  in IEEE Int. Work. on Inf. Forensics and Security (WIFS), 2011, pp. 1–6.
  * [14] Li Weng, Laurent Amsaleg, and Teddy Furon,  “Privacy-preserving outsourced media search,”  IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 10, pp. 2738–2751, 2016.
  * [15] Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra,  “Privacy via the johnson-lindenstrauss transform,”  arXiv preprint arXiv:1204.2606, 2012.
  * [16] Shantanu Rane and Petros T Boufounos,  “Privacy-preserving nearest neighbor methods: Comparing signals without revealing them,”  IEEE Signal Processing Magazine, vol. 30, no. 2, pp. 18–28, 2013\.
  * [17] Hervé Jégou, Matthijs Douze, and Cordelia Schmid,  “On the burstiness of visual elements,”  in IEEE Conf. on Comp. Vision and Pattern Recog. (CVPR), 2009, pp. 1169–1176.
  * [18] Florent Perronnin and Christopher Dance,  “Fisher kernels on visual vocabularies for image categorization,”  in IEEE Conf. on Comp. Vision and Pattern Recog. (CVPR), 2007, pp. 1–8.
  * [19] Hervé Jégou, Matthijs Douze, Cordelia Schmid, and Patrick Pérez,  “Aggregating local descriptors into a compact image representation,”  in IEEE Conf. on Comp. Vision and Pattern Recog. (CVPR), 2010, pp. 3304–3311.
  * [20] Artem Babenko, Anton Slesarev, Alexandr Chigorin, and Victor Lempitsky,  “Neural codes for image retrieval,”  in Europ.  Conf.  on Comp.  Vision. Springer, 2014, pp. 584–599.
  * [21] Diederik P Kingma and Max Welling,  “Auto-encoding variational bayes,”  in International Conference on Learning Representations (ICLR), 2014\.
  * [22] Saiprasad Ravishankar and Yoram Bresler,  “Learning sparsifying transforms,”  IEEE Trans. on Signal Processing, vol. 61, no. 5, pp. 1072–1086, 2013.
  * [23] Marzieh Gheisari, Teddy Furon, and Laurent Amsaleg,  “Joint learning of assignment and representation for biometric group membership,”  in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2020, pp. 2922–2926.
  * [24] Marzieh Gheisari, Teddy Furon, and Laurent Amsaleg,  “Group membership verification with privacy: Sparse or dense?,”  in 2019 IEEE International Workshop on Information Forensics and Security (WIFS). IEEE, 2019, pp. 1–7.
  * [25] Marzieh Gheisari, Teddy Furon, Laurent Amsaleg, Behrooz Razeghi, and Slava Voloshynovskiy,  “Aggregation and embedding for group membership verification,”  in ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2019, pp. 2592–2596.
  * [26] Dimche Kostadinov, Slava Voloshynovskiy, and Sohrab Ferdowsi,  “Learning overcomplete and sparsifying transform with approximate and exact closed form solutions,”  in European Workshop on Visual Information Processing, 2018.
  * [27] Behrooz Razeghi, Slava Voloshynovskiy, Dimche Kostadinov, and Olga Taran,  “Privacy preserving identification using sparse approximation with ambiguization,”  in IEEE Int. Work. on Info. Forensics and Security (WIFS), 2017, pp. 1–6.
  * [28] Yann LeCun and Corinna Cortes,  “MNIST handwritten digit database,”  2010\.
  * [29] Han Xiao, Kashif Rasul, and Roland Vollgraf,  “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,”  arXiv preprint arXiv:1708.07747, 2017.
  * [30] Alex Krizhevsky, Geoffrey Hinton, et al.,  “Learning multiple layers of features from tiny images,”  2009\.
  * [31] Laurens van der Maaten and Geoffrey Hinton,  “Visualizing data using t-sne,”  Journal of machine learning research, vol. 9, no. Nov, pp. 2579–2605, 2008.


# Packings in bipartite prisms and hypercubes

Boštjan Brešara,b Sandi Klavžara,b,c Douglas F. Ralld

###### Abstract

The $2$-packing number $\rho_{2}(G)$ of a graph $G$ is the cardinality of a
largest $2$-packing of $G$ and the open packing number $\rho^{\rm o}(G)$ is
the cardinality of a largest open packing of $G$, where an open packing (resp.
$2$-packing) is a set of vertices in $G$ no two (closed) neighborhoods of
which intersect. It is proved that if $G$ is bipartite, then $\rho^{\rm
o}(G\,\square\,K_{2})=2\rho_{2}(G)$. For hypercubes, the lower bounds
$\rho_{2}(Q_{n})\geq 2^{n-\lfloor\log n\rfloor-1}$ and $\rho^{\rm
o}(Q_{n})\geq 2^{n-\lfloor\log(n-1)\rfloor-1}$ are established. These findings
are applied to injective colorings of hypercubes. In particular, it is
demonstrated that $Q_{9}$ is the smallest hypercube which is not perfect
injectively colorable. It is also proved that $\gamma_{t}(Q_{2^{k}}\times
H)=2^{2^{k}-k}\gamma_{t}(H)$, where $H$ is an arbitrary graph with no isolated
vertices.

a Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

c Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

d Department of Mathematics, Furman University, Greenville, SC, USA

Keywords: $2$-packing number, open packing number, bipartite prism, hypercube,
injective coloring, (total) domination number

AMS Subj. Class. (2020): 05C69, 05C76

##  1 Introduction

For many reasons, hypercubes are ubiquitous in theoretical computer science
and in combinatorics. Understanding their structure is therefore a fundamental
problem. Although hypercubes have a seemingly simple structure, we quickly
encounter very complex problems. For instance, one of them was the middle
levels problem, which was successfully dismissed [15]. On the other hand, the
problem of determining the domination number of hypercubes is beyond the reach
of existing methods. To date, exact values of $\gamma(Q_{n})$ are only known
for $n\leq 9$, where the value $\gamma(Q_{9})=62$ was obtained in [16], and
for the following two infinite families.

######  Theorem 1.1.

([7, 19]) If $k\geq 1$, then $\gamma(Q_{2^{k}-1})=2^{2^{k}-k-1}$ and
$\gamma(Q_{2^{k}})=2^{2^{k}-k}$.

The values $\gamma(Q_{2^{k}-1})=2^{2^{k}-k-1}$ can be obtained from the fact
that hypercubes $Q_{2^{k}-1}$ admit 1-perfect codes, in which case the
domination number coincides with the cardinality of a 1-perfect code.

The most important variation of the domination number is the total domination
number; see a recent monograph [8] surveying domination theory with the two
invariants in the central role. Roughly speaking, domination operates with
closed neighborhoods while total domination with open neighborhoods, which
often causes a different behavior of the invariants. However, as proved in [1]
by using hypergraph transversals, $\gamma_{t}(Q_{n+1})=2\gamma(Q_{n})$ for all
$n$, which makes the domination number and the total domination number in
hypercubes tightly connected. More generally, the authors of [1] proved that
$\gamma_{t}(G\,\square\,K_{2})=2\gamma(G)$ as soon as $G$ is a bipartite
graph.

The concepts of packing number and open packing number of a graph are often
used in domination theory, since they present natural lower bounds on the
domination number and the total domination number, respectively, of the graph.
The concept of packing was used back in 1975 by Meir and Moon in their
classical theorem stating that in a tree the domination number equals the
packing number [11]. On the other hand, open packing was introduced by Henning
and Slater [9], and was later used in [18] to prove a canonical formula for
the total domination number of the direct product of two graphs, which holds
if one of the factors has the total domination number equal to its open
packing number. Similarly as total domination is related to domination, open
packing can be regarded as a version of packing in which closed neighborhoods
are replaced with open neighborhoods. See [12, 13, 14] for some recent studies
of (open) packings as well as [5] for their application.

Open packings are also related to the so-called injective colorings of graphs,
cf. [17]. More precisely, an injective coloring of a graph is exactly a
partition of its vertex set into open packings. In a recent paper [3], graphs
that admit injective colorings such that each of the color classes is a
maximum open packing were considered. While proving this property for
hypercubes of some small dimensions, it was also proved for those whose
dimension is a power of $2$. Yet, nothing else was known, including whether
there exists a hypercube that does not satisfy this property. One of the
reasons for the difficulty of this question is that the open packing number
(i.e., the cardinality of a maximum open packing) has not been known.

We proceed as follows. In the remainder of this introduction, we provide the
definitions and concepts we need for the following. In Section 2 we prove that
the open packing number of a prism over a bipartite graph $G$ is twice the
$2$-packing number of $G$. This result nicely complements [1, Theorem 1] which
states that the total domination number of a prism over a bipartite graph $G$
is twice the domination number of $G$. We also demonstrate that in general,
the open packing number of a prism over a graph $G$ can be arbitrary larger
that the $2$-packing number of $G$. In Section 3 we prove lower bounds on the
$2$-packing number and the open packing number of hypercubes. The bounds are
sharp for small dimensions and for two infinite families, but are not sharp in
general. In the subsequent section we apply these findings to injective
colorings of hypercubes. In particular we demonstrate that $Q_{9}$ is the
smallest hypercube which is not perfect injectively colorable. In the
concluding remarks, we give an overview of the known values for the hypercube
invariants considered here and also derive the total domination number of the
direct product of $Q_{2^{k}}$ and an arbitrary graph.

###  1.1 Preliminaries

Let $G=(V(G),E(G))$ be a graph and $x\in V(G)$. The open neighborhood $N(x)$
is the set of vertices adjacent to $x$ and the closed neighborhood is
$N[x]=N(x)\cup\\{x\\}$. A set $D\subseteq V(G)$ is a dominating set of $G$ if
each vertex of $V(G)\setminus D$ has a neighbor in $D$. The cardinality of a
smallest dominating set of $G$ is the domination number $\gamma(G)$ of $G$.
Similarly, $D\subseteq V(G)$ is a total dominating set of $G$ if each vertex
of $V(G)$ has a neighbor in $D$. The cardinality of a smallest dominating set
of $G$ is the total domination number $\gamma_{t}(G)$ of $G$.

Let $X\subseteq V(G)$. Then $X$ is a $2$-packing of $G$ if $N[x]\cap
N[y]=\emptyset$ for every pair of distinct vertices $x,y\in X$. Similarly, if
$N(x)\cap N(y)=\emptyset$ for every pair of distinct vertices $x,y\in X$, then
$X$ is an open packing of $G$. The cardinality of a largest $2$-packing of $G$
is the $2$-packing number $\rho_{2}(G)$ of $G$ and the cardinality of a
largest open packing of $G$ is the open packing number $\rho^{\rm o}(G)$ of
$G$. By a $\rho_{2}$-set of $G$ we mean a $2$-packing of $G$ of cardinality
$\rho_{2}(G)$. A $\rho^{\rm o}$-set of $G$ is defined analogously.

If $X$ is a $2$-packing such that $V(G)=\cup_{x\in X}N[x]$ then we say that
$X$ is a $1$-perfect code of $G$. In domination theory, 1-perfect codes are
known as efficient dominating sets, see [8, Chapter 9] and [10]. Since
$\gamma(G)\geq\rho_{2}(G)$ for every graph $G$, if $X$ is a $1$-perfect code
of $G$, then $X$ is also a dominating set of $G$. This observation leads to
the following well known fact.

######  Proposition 1.2.

If $G$ admits a $1$-perfect code, then $\gamma(G)=\rho_{2}(G)$. If in addition
$G$ is $r$-regular, then $\gamma(G)=\rho_{2}(G)=\frac{n(G)}{r+1}$.

The _Cartesian product_ $G\,\square\,H$ of graphs $G$ and $H$ is the graph
whose vertex set is $V(G)\times V(H)$, and two vertices $(g_{1},h_{1})$ and
$(g_{2},h_{2})$ are adjacent in $G\,\square\,H$ if either $g_{1}=g_{2}$ and
$h_{1}h_{2}$ is an edge in $H$ or $h_{1}=h_{2}$ and $g_{1}g_{2}$ is an edge in
$G$. For a vertex $g$ of $G$, the subgraph of $G\,\square\,H$ induced by the
set $\\{(g,h):\,h\in V(H)\\}$ is an _$H$ -fiber_ and is denoted by
${}^{g}\\!H$. Similarly, for $h\in H$, the _$G$ -fiber_, $G^{h}$, is the
subgraph induced by $\\{(g,h):\,g\in V(G)\\}$. Cartesian product is
commutative and associative. The hypercube of dimension $n$, or the $n$-cube,
is isomorphic to $K_{2}\,\square\,\cdots\,\square\,K_{2}$, where there are $n$
factors $K_{2}$, and is denoted by $Q_{n}$. The equality
$Q_{n}=Q_{n-1}\,\square\,K_{2}$ will be used (at least implicitly) several
times in the paper. Finally, the _direct product_ $G\times H$ of graphs $G$
and $H$ has the vertex set $V(G)\times V(H)$, and two vertices $(g_{1},h_{1})$
and $(g_{2},h_{2})$ are adjacent in $G\times H$ if $g_{1}g_{2}$ is an edge in
$G$ and $h_{1}h_{2}$ is an edge in $H$.

##  2 Packing vs. open packing in bipartite prisms

In [1] it was proved that if $G$ is a bipartite graph, then
$\gamma_{t}(G\,\square\,K_{2})=2\gamma(G)$. In this section we prove an
analogous result that connects the open packing number and the packing number.

We begin with the following simple lemma, which holds in all graphs.

######  Lemma 2.1.

If $G$ is a graph, then $\rho^{\rm o}(G\,\square\,K_{2})\geq 2\rho_{2}(G)$.

###### Proof.

Let $G$ be a graph, and let $P$ be a $\rho_{2}$-set of $G$. Then $P\times
V(K_{2})$ is an open packing of $G\,\square\,K_{2}$, hence the result. ∎

In general, $\rho^{\rm o}(G\,\square\,K_{2})$ can be arbitrary larger than
$2\rho_{2}(G)$. For an example consider the family of graphs $G_{k}$, $k\geq
1$, defined as follows. $G_{k}$ contains $2k$ disjoint cycles $C_{5}$
connected in a row by an edge between two consecutive $5$-cycles. This
informal definition of $G_{k}$ should be clear from Fig. 1 where
$G_{2}\,\square\,K_{2}$ is drawn. As an arbitrary packing of $G_{k}$ contains
at most one vertex of each $C_{5}$ we infer that $\rho_{2}(G_{k})=2k$. On the
other hand, repeating the pattern as shown in Fig. 1 for $k=2$, we get
$\rho^{\rm o}(G_{k}\,\square\,K_{2})\geq 5k$.

Figure 1: An open packing in $G_{2}\,\square\,K_{2}$

For bipartite graphs, however, the above phenomena cannot occur as the main
result of this section asserts.

######  Theorem 2.2.

If $G$ is a bipartite graph, then $\rho^{\rm
o}(G\,\square\,K_{2})=2\rho_{2}(G)$.

###### Proof.

Let $G$ be a bipartite graph with parts $A$ and $B$ forming the natural
partition of $V(G)$. By Lemma 2.1, we have $\rho^{\rm
o}(G\,\square\,K_{2})\geq 2\rho_{2}(G)$. To prove the reversed inequality,
consider an open packing $O$ in $G\,\square\,K_{2}$ such that $|O|=\rho^{\rm
o}(G\,\square\,K_{2})$. We will show that $O$ can be transformed into an open
packing $O^{\prime}$ of the form $P^{\prime}\times V(K_{2})$, where
$P^{\prime}$ is a subset of $V(G)$. (Clearly, the latter also implies that
$P^{\prime}$ is a $2$-packing.) Note that $O$ can be presented as the disjoint
union $I\cup R$, where $I$ is the set of vertices that are isolated in the
subgraph of $G\,\square\,K_{2}$ induced by $O$, while $R$ is the set of
vertices that have exactly one neighbor in $O$. Clearly, at least one of the
sets $I$ or $R$ is non-empty. Set $V(K_{2})=\\{1,2\\}$, and let $I_{i}=I\cap
V(G^{i})$ and $R_{i}=R\cap V(G^{i})$ for all $i\in[2]$. In addition, let
$I_{i}^{A}=\\{(u,i)\in I_{i}:\,u\in A\\}$, $I_{i}^{B}=\\{(u,i)\in I_{i}:\,u\in
B\\}$ for $i\in[2]$, and similarly let $R_{i}^{A}=\\{(u,i)\in R_{i}:\,u\in
A\\}$, $R_{i}^{B}=\\{(u,i)\in R_{i}:\,u\in B\\}$ for $i\in[2]$. Next, we
compare the two quantities $|I_{1}^{A}|+|I_{2}^{B}|$ and
$|I_{2}^{A}|+|I_{1}^{B}|$. We may assume with no loss of generality that
$|I_{1}^{A}|+|I_{2}^{B}|\geq|I_{2}^{A}|+|I_{1}^{B}|$. Now, the announced
transformation of $O$ to $O^{\prime}$ is defined as follows:

  * •

if $(u,t)\in I_{1}^{A}\cup I_{2}^{B}$, then let $\\{u\\}\times
V(K_{2})\subseteq O^{\prime}$;

  * •

if $(u,t)\in I_{2}^{A}\cup I_{1}^{B}$, then let $(\\{u\\}\times V(K_{2}))\cap
O^{\prime}=\emptyset$;

  * •

if $(u,1)\in R_{1}$ and $(u,2)\in R_{2}$, then let $\\{u\\}\times
V(K_{2})\subseteq O^{\prime}$;

  * •

if $(u,1)\in R_{1}^{A}$ and $(v,1)\in R_{1}^{B}$, where $uv\in E(G)$, then let
$\\{u\\}\times V(K_{2})\subseteq O^{\prime}$ and $(\\{v\\}\times V(K_{2}))\cap
O^{\prime}=\emptyset$;

  * •

if $(u,2)\in R_{2}^{A}$ and $(v,2)\in R_{2}^{B}$, where $uv\in E(G)$, then let
$\\{v\\}\times V(K_{2})\subseteq O^{\prime}$ and $(\\{u\\}\times V(K_{2}))\cap
O^{\prime}=\emptyset$.

We claim that $|O^{\prime}|\geq|O|$. Indeed, the first two rows in the above
transformation show that for every vertex $(u,t)\in I_{1}^{A}\cup I_{2}^{B}$
we get two vertices in $O^{\prime}$, while for every vertex $(u,t)\in
I_{2}^{A}\cup I_{1}^{B}$ we get no vertices in $O^{\prime}$, yet
$|I_{1}^{A}\cup I_{2}^{B}|>|I_{2}^{A}\cup I_{1}^{B}|$ by the earlier
assumption. By the last three rows of the above transformation, every pair of
vertices in $R$ is replaced by two vertices in $O^{\prime}$. This altogether
implies that $|O^{\prime}|\geq|O|$, so it remains to prove that $O^{\prime}$
is an open packing in $G\,\square\,K_{2}$.

If $(u,1)\in I_{1}^{A}$ and $(v,1)\in I_{1}^{A}$, then $d_{G}(u,v)\geq 4$,
because the vertices belong to $O$, which is an open packing, and $u$ and $v$
are both in $A$. Thus vertices in $\\{u\\}\times V(K_{2})$ will be at distance
at least $4$ from the vertices in $\\{v\\}\times V(K_{2})$. By symmetry, we
get the same conclusion for vertices $(u,2)\in I_{2}^{B}$ and $(v,2)\in
I_{2}^{B}$. If $(u,1)\in I_{1}^{A}$ and $(v,2)\in I_{2}^{B}$, then
$d_{G}(u,v)\geq 3$, because $u$ and $v$ belong to different parts, $A$ and $B$
respectively, of the bipartition of $V(G)$ and they belong to $O$, which is an
open packing. Thus, vertices in $\\{u\\}\times V(K_{2})$ will be at distance
at least $3$ from the vertices in $\\{v\\}\times V(K_{2})$, as desired.
Clearly, if $(u,t)\in I_{1}^{A}\cup I_{2}^{B}$, then $d_{G}(u,v)\geq 3$ for
any $v\in V(G)$ such that $\\{(v,1),(v,2)\\}\subset R$. This yields that
vertices in $\\{u\\}\times V(K_{2})$ will be at distance at least $3$ from the
vertices in $\\{v\\}\times V(K_{2})$. If $(u,1)\in I_{1}^{A}$ and $(v,1)\in
R_{1}^{A}$, we have $d_{G}(u,v)\geq 4$. On the other hand, if $(u,1)\in
I_{1}^{A}$ and $(v,2)\in R_{2}^{B}$ we have $d_{G}(u,v)\geq 3$. In either
case, the corresponding vertices in $O^{\prime}$ are at least three apart. By
symmetry, we can find that for vertices in $I_{2}^{B}$ and vertices in
$R_{1}^{A}\cup R_{2}^{B}$ their distances are sufficiently large so that the
corresponding $K_{2}$-fibers that are in $O^{\prime}$ will be at distance at
least $3$. This completes the proof that the distance between the vertices in
$O^{\prime}$ that appear in the first row of the above transformation to all
other vertices in $O^{\prime}$ will be at least $3$, except of course for two
vertices in $O^{\prime}$ that belong to the same $K_{2}$-fiber and are
adjacent.

Vertices of $O^{\prime}$ that appear in the third row of the transformation
remain at distance at least $3$ from all other vertices in $O^{\prime}$ (with
the clear exception of two adjacent such vertices). Therefore, it remains to
consider the vertices in $O^{\prime}$ that appear in the last two rows of the
above transformation. Suppose there are two vertices in $R_{1}^{A}$ (and a
similar argument can be applied if they are in $R_{2}^{B}$), say, $(u,1)$ and
$(v,1)$, which are not adjacent. Then $d_{G}(u,v)\geq 4$, and so
$\\{u\\}\times V(K_{2})$ will be at distance at least $4$ from the vertices in
$\\{v\\}\times V(K_{2})$ (by symmetry, the same conclusion applies if $(u,2)$
and $(v,2)$ are in $R_{2}^{B}$). Finally, let $(u,1)\in R_{1}^{A}$ and
$(v,2)\in R_{2}^{B}$. Since $O$ is an open packing, we have $d_{G}(u,v)>1$,
and since they are in different parts of the bipartition, we get
$d_{G}(u,v)\geq 3$. We derive that $\\{u\\}\times V(K_{2})$ will be at
distance at least $3$ from the vertices in $\\{v\\}\times V(K_{2})$, which
concludes the proof that $O^{\prime}$ is an open packing. Since $|O|=\rho^{\rm
o}(G\,\square\,K_{2})$ and $|O^{\prime}|\geq|O|$, we derive
$|O^{\prime}|=|O|=\rho^{\rm o}(G\,\square\,K_{2})$. In addition, there exists
a set $P^{\prime}\subset V(G)$ such that $O^{\prime}=P^{\prime}\times[2]$,
where $P^{\prime}$ is a $2$-packing of $G$. Hence,
$|P^{\prime}|\leq\rho_{2}(G)$, and so $|O^{\prime}|=2|P^{\prime}|\leq
2\rho_{2}(G)$, implying $\rho^{\rm o}(G\,\square\,K_{2})\leq 2\rho_{2}(G)$. ∎

##  3 (Open) packings in hypercubes

The following lemma follows by observing that the restriction of a 2-packing
in $G\,\square\,K_{2}$ to a $G$-layer is a 2-packing of that layer.

######  Lemma 3.1.

If $G$ is a graph, then $\rho_{2}(G\,\square\,K_{2})\leq 2\rho_{2}(G)$.

We can now bound $\rho_{2}$ and $\rho^{\rm o}$ of hypercubes as follows.

######  Theorem 3.2.

If $n\geq 2$, then

  1. (i)

$\rho_{2}(Q_{n})\geq 2^{n-\lfloor\log n\rfloor-1}$ and

  2. (ii)

$\rho^{\rm o}(Q_{n})\geq 2^{n-\lfloor\log(n-1)\rfloor-1}$.

###### Proof.

(i) Suppose first that $n=2^{k}-1$, where $k\geq 2$. As already mentioned, in
these cases $Q_{n}$ admits a $1$-perfect code, say $S$. Then
$|S|=2^{2^{k}-1}/2^{k}=2^{2^{k}-k-1}$ and consequently

$\rho_{2}(Q_{n})=|S|=2^{2^{k}-k-1}=2^{2^{k}-1-(k-1)-1}=2^{n-\lfloor\log
n\rfloor-1}\,.$

Consider now the hypercubes $Q_{n}$, where $k\geq 3$ and
$2^{k-1}-1<n<2^{k}-1$. In particular, if $n=2^{k}-2$, then since
$Q_{2^{k}-1}=Q_{2^{k}-2}\,\square\,K_{2}$, Lemma 3.1 implies that

$\rho_{2}(Q_{n})=\rho_{2}(Q_{2^{k}-2})\geq\frac{1}{2}\rho_{2}(Q_{2^{k}-1})=2^{2^{k}-k-2}=2^{2^{k}-2-(k-1)-1}=2^{n-\lfloor\log
n\rfloor-1}\,.$

Inductively applying the lemma, the result holds for all $n$ such that
$2^{k-1}-1<n<2^{k}-1$. Therefore, (i) holds for all $n\geq 2$.

(ii) Applying Theorem 2.2 and (i), we have

$\rho^{\rm o}(Q_{n})=2\rho_{2}(Q_{n-1})\geq 2\cdot
2^{(n-1)-\lfloor\log(n-1)\rfloor-1}=2^{n-\lfloor\log(n-1)\rfloor-1}$

for all $n\geq 2$ and we are done. ∎

If $n\leq 7$, then equality holds in Theorem 3.2(i). The cases when
$n\in\\{2,3,4\\}$ can be easily argued by case analysis. The equality in cases
when $n\in\\{5,6\\}$ then follow by combining Lemma 3.1 and Theorem 3.2(i).
For $n=7$, the equality holds because $Q_{7}$ has a $1$-perfect code. One is
thus tempted to conjecture that the lower bound in Theorem 3.2(i) holds for
all $n$. However, with the help of a computer, we found the set

$\displaystyle T=\ $
$\displaystyle\\{00000000,00001110,00110010,00111100,01010110,01011000,$
$\displaystyle\ 01100100,01101001,01111111,10010100,10100101,10101011,$
$\displaystyle\ 11000111,11001100,11011011,11100010,11110001\\}$

which is a 2-packing in $Q_{8}$ with $|T|=17$, hence $\rho_{2}(Q_{8})\geq 17$.
By Theorem 2.2, this in turn implies that $\rho^{\rm o}(Q_{9})\geq 34$. Hence
also the lower bound in Theorem 3.2(ii) is not sharp in general. It is sharp
however for all $n\leq 8$ because the lower bound in Theorem 3.2(i) is sharp
for $n\leq 7$ and because of Theorem 2.2. Furthermore, by using Theorem 2.2
and the fact that the lower bound in Theorem 3.2(i) is sharp when $n=2^{k}-1$,
it follows that the lower bound in Theorem 3.2(ii) is sharp for each value of
$n$ that is a power of $2$.

##  4 Application to injective colorings

An injective coloring of a graph $G$ is a partition of the vertex set of $G$
into open packings. The injective chromatic number, $\chi_{i}(G)$, of $G$ is
the minimum cardinality of an injective coloring in $G$. The concept was
introduced by Hahn, Kratochvíl, Širáň and Sotteau [6] back in 2002, and has
been considered by a number of authors, cf. [2, 4]. In the recent paper [3],
graphs that admit special types of injective colorings were considered: a
graph $G$ is a _perfect injectively colorable graph_ if it has an injective
coloring in which every color class forms a $\rho^{\rm o}$-set of $G$. The
authors of [3] considered hypercubes that are perfect injectively colorable.
They noticed that such are the hypercubes $Q_{n}$, where $n\in[5]$, and proved
that for all $k\in\mathbb{N}$, the hypercube $Q_{2^{k}}$ is a perfect
injectively colorable graph. Apart from the mentioned cases, it was asked in
[3, Problem 1] in which other dimensions the hypercube is perfect injectively
colorable. Since an answer to the question is closely related to computing the
value of the open packing number of hypercubes, it was also asked in [3,
Problem 2] what is the value of $\rho^{\rm o}(Q_{n})$ for $n\geq 6$.

$3$$4$$1$$2$$2$$4$$1$$3$$7$$8$$5$$6$$6$$8$$5$$7$$8$$6$$7$$5$$5$$6$$7$$8$$4$$2$$3$$1$$1$$2$$3$$4$$6$$5$$8$$7$$7$$5$$8$$6$$2$$1$$4$$3$$3$$1$$4$$2$$1$$3$$2$$4$$4$$3$$2$$1$$5$$7$$6$$8$$8$$7$$6$$5$
Figure 2: Partition of $V(Q_{6})$ into (maximum) $2$-packings of $Q_{6}$.

In this note, we give some partial answers to the above two questions. One can
easily find that $\rho_{2}(Q_{5})=4$, which by Theorem 2.2 implies that
$\rho^{\rm o}(Q_{6})=8$. In addition, Fig. 2 shows a maximum $2$-packing of
$Q_{6}$ of cardinality $8$, where vertices of an arbitrary color in $[8]$ form
a maximum $2$-packing. This gives, again by Theorem 2.2, that $\rho^{\rm
o}(Q_{7})=16$. In addition, recall that $\rho^{\rm o}(Q_{8})=32$, which
follows from the fact that $Q_{7}$ has a perfect code. Now, by the observation
from Section 3, we have $\rho_{2}(Q_{8})\geq 17$. On the other hand, we claim
that $\rho_{2}(Q_{8})\leq 30$. Suppose to the contrary that
$\rho_{2}(Q_{8})>30$, and let $P$ be a $\rho_{2}$-set of $Q_{8}$. Then,
partitioning $V(Q_{8})$ into $Q$ and $Q^{\prime}$, each of which induces
$Q_{7}$, we infer that either $|Q\cap P|$ or $|Q^{\prime}\cap P|$ is equal to
$16$. We may assume that $|Q\cap P|=16$, and noting that $Q\cap P$ is a
$2$-packing of $Q_{7}$, this implies that $Q\cap P$ corresponds to a perfect
code of $Q_{7}$, thus $Q\cap P$ is a dominating set of $Q$. This in turn
implies that every vertex in $Q^{\prime}$ is at distance at most $2$ from a
vertex in $Q\cap P$, which yields that $P=Q\cap P$, and so $|P|=16$, a
contradiction proving that $\rho_{2}(Q_{8})\leq 30$. Now, using Theorem 2.2,
we get $34\leq\rho^{\rm o}(Q_{9})\leq 60$. In particular, $\rho^{\rm
o}(Q_{9})$ is not a power of $2$, which readily implies that $Q_{9}$ does not
admit a partition into $\rho^{\rm o}$-sets, and is consequently not a perfect
injectively colorable graph. On the other hand, refer to Fig. 2 again, which
shows a coloring of $Q_{6}$ in which each color class is a $2$-packing of
cardinality $\rho_{2}(Q_{6})$. By applying Theorem 2.2 and the first part of
its proof, one can construct an injective coloring of $Q_{7}$ in which each
color class is a open packing of cardinality $\rho^{\rm o}(Q_{7})$. Therefore,
$Q_{7}$ is perfect injectively colorable graph.

Summarizing the above, hypercubes $Q_{n}$, where $n\leq 8$, are perfect
injectively colorable graphs, and so $Q_{9}$ is the first instance of a
hypercube, which is not in this class of graphs.

##  5 Concluding remarks

Table 1 presents values or bounds on the main domination and packing
invariants in hypercubes $Q_{n}$, for all $n,n\leq 9$. The values for $\gamma$
and $\gamma_{t}$ have been known earlier, while some of the values and bounds
for $\rho_{2}$ and $\rho^{\rm o}$ have been obtained in this paper.

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
$\gamma$ | 1 | 2 | 2 | 4 | 7 | 12 | 16 | 32 | 62
$\gamma_{t}$ | 2 | 2 | 4 | 4 | 8 | 14 | 24 | 32 | 64
$\rho_{2}$ | 1 | 1 | 2 | 2 | 4 | 8 | 16 | 17-30 | ?
$\rho^{\rm o}$ | 2 | 2 | 2 | 4 | 4 | 8 | 16 | 32 | 34-60
Table 1: Packing and domination invariants in hypercubes $Q_{n}$, where
$n<10$.

In addition, consider the value $\gamma_{t}(Q_{2^{k}})=2^{2^{k}-k}$, which
follows from Theorem 1.1 combined with the formula
$\gamma_{t}(G\,\square\,K_{2})=2\gamma(G)$ from [1]. Now, compare this with
the bound $\rho^{\rm o}(Q_{2^{k}})\geq 2^{2^{k}-k}$, which follows from
Theorem 3.2(ii) when plugging $n=2^{k}$. Since $\gamma_{t}(G)\geq\rho^{\rm
o}(G)$ for every graph $G$ with no isolated vertices, we infer that

$\gamma_{t}(Q_{2^{k}})=2^{2^{k}-k}=\rho^{\rm o}(Q_{2^{k}}),\textrm{ for all
}k\in\mathbb{N}.$ (1)

Recall the result from [18] stating that $\gamma_{t}(G\times
H)=\gamma_{t}(G)\gamma_{t}(H)$ whenever $G$ is a graph with $\rho^{\rm
o}(G)=\gamma_{t}(G)$ and graphs $G$ and $H$ have no isolated vertices.
Therefore, from the discussion above we get that

$\gamma_{t}(Q_{2^{k}}\times H)=2^{2^{k}-k}\gamma_{t}(H)\,,$

where $k\in\mathbb{N}$ and $H$ is an arbitrary graph with no isolated
vertices. An additional family of graphs with this property (that
$\gamma_{t}=\rho^{\rm o}$) can be found in [12]. It would be interesting to
establish if there are any hypercubes $Q_{n}$ of other dimensions than those
in (1) that satisfy the equality $\gamma_{t}(Q_{n})=\rho^{\rm o}(Q_{n})$.

## Acknowledgments

This work was performed within the bilateral grant ‘Domination in graphs,
digraphs and their products” (BI-US/22-24-038). B.B. and S.K. were supported
by the Slovenian Research Agency (ARRS) under the grants P1-0297, J1-2452,
N1-0285, and J1-3002.

## References

  * [1] J. Azarija, M.A. Henning, S. Klavžar, (Total) domination in prisms, Electron. J. Combin. 24 (2017) Paper 1.19.
  * [2] C. Brause, P. Golovach, B. Martin, P. Ochem, D. Paulusma, S. Smith, Acyclic, star, and injective colouring: bounding the diameter, Electron. J. Combin. 29 (2022) Paper 2.43.
  * [3] B. Brešar, B. Samadi, I.G. Yero, Injective coloring of graphs revisited, Discrete Math. 346 (2023) Paper 113348.
  * [4] M. Chen, G. Hahn, A. Raspaud, W. Wang, Some results on the injective chromatic number of graphs, J. Comb. Optim. 24 (2012) 299–318.
  * [5] Y. Gao, E. Zhu, Z. Shao, I. Gutman, A. Klobučar, Total domination and open packing in some chemical graphs, J. Math. Chem. 56 (2018) 1481–1492.
  * [6] G. Hahn, J. Kratochvíl, J. Širáň, D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256 (2002) 179–192.
  * [7] F. Harary, M. Livingston, Independent domination in hypercubes. Appl. Math. Lett. 6 (1993) 27–28.
  * [8] T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Domination in Graphs–Core Concepts, Springer Monographs in Mathematics, Springer, Cham, 2023.
  * [9] M.A. Henning, P.J. Slater, Open packing in graphs, J. Combin. Math. Combin. Comput. 28 (1999) 5–18.
  * [10] M. Knor, P. Potočnik, Efficient domination in cubic vertex-transitive graphs, European J. Combin. 33 (2012) 1755–1764.
  * [11] A. Meir, J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225–233.
  * [12] M. Mohammadi, M. Maghasedi, A note on the open packing number in graphs, Math. Bohem. 144 (2019) 221–224.
  * [13] D.A. Mojdeh, I. Peterin, B. Samadi, I.G. Yero, (Open) packing number of some graph products, Discrete Math. Theor. Comput. Sci. 22 (2020) Paper 1.
  * [14] D.A. Mojdeh, B. Samadi, I.G. Yero, Further results on packing related parameters in graphs, Discuss. Math. Graph Theory 42 (2022) 333–348.
  * [15] T. Mütze, Proof of the middle levels conjecture, Proc. Lond. Math. Soc. 112 (2016) 677–713.
  * [16] P.R.J. Östergård, U. Blass, On the size of optimal binary codes of length $9$ and covering radius $1$. IEEE Trans. Inform. Theory 47 (2001) 2556–2557.
  * [17] B.S. Panda, Priyamvada, Injective coloring of some subclasses of bipartite graphs and chordal graphs, Discrete Appl. Math. 291 (2021) 68–87.
  * [18] D. F. Rall, Total domination in categorical products of graphs, Discuss. Math. Graph Theory 25 (2005) 35–44.
  * [19] G.J.M. van Wee, Improved sphere bounds on the covering radius of codes, IEEE Trans. Inform. Theory 34 (1988) 237–245.


Arising from X. Deng et al. Nature Communications
https://doi.org/10.1038/s41467-019-10257-2 (2019)

# Extracting Kondo temperature of strongly-correlated systems from the inverse
local magnetic susceptibility

A. A. Katanin  Center for Photonics and 2D Materials, Moscow Institute of
Physics and Technology, Institutsky lane 9, Dolgoprudny, 141700, Moscow
region, Russia
M. N. Mikheev Institute of Metal Physics, Kovalevskaya str. 18, 620990,
Ekaterinburg, Russia

††preprint:

The temperature scales of screening of local magnetic and orbital moments are
important characteristics of strongly correlated substances. In a recent paper
X. Deng et al. paper  using dynamic mean-field theory (DMFT) have identified
temperature scales of the onset of screening in orbital and spin channels in
some correlated metals from the deviation of temperature dependence of local
susceptibility from the Curie law. We argue that the scales obtained this way
are in fact much larger, than the corresponding Kondo temperatures, and,
therefore, do not characterize the screening process. By reanalyzing the
results of this paper we find the characteristic (Kondo) temperatures for
screening in the spin channel $T_{K}\approx 100$ K for V2O3 and $T_{K}\approx
350$ K for Sr2RuO4, which are almost an order of magnitude smaller than those
for the onset of the screening estimated in the paper ($1000$ K and $2300$ K,
respectively); for V2O3 the obtained temperature scale $T_{K}$ is therefore
comparable to the temperature of completion of the screening, $T^{\rm
comp}\sim 25$ K, which shows that the screening in this material can be
described in terms of a single temperature scale.

X. Deng et al. paper  have performed a detailed analysis of the temperature
dependence of orbital and magnetic local susceptibilities of two strongly
correlated materials, Sr2RuO4 and V2O3 within DMFT DMFT ; DMFT2 . At high
temperatures the susceptibilities obey the Curie law, $\chi(T)\sim 1/T$. The
temperatures $T^{\rm ons}$ of the onset of screening of spin- and orbital
local moments are obtained from the deviation of $T\chi(T)$ from a constant
value. Corresponding temperature scales $T^{\rm ons}$ are found to be much
larger than the scales, corresponding to the completed screening (onset of the
Fermi-liquid behavior) $T^{\rm cmp}\sim 25$ K.

In the following we argue however that the temperatures $T^{\rm ons}$,
obtained by the authors, do not correspond to the temperature scales of the
spin screening. Indeed, instead of considering the quantity $T\chi(T)$, we
plot inverse spin susceptibility $\chi^{-1}(T)$ for both considered compounds,
Sr2RuO4 and V2O3 on the basis of the data of the paper (see Fig. 1). For
Sr2RuO4 (see Fig. 1a) we do not find any peculiarity at the onset temperature
$T^{\rm ons}=2300$ K suggested by the authors. Instead, at all considered
temperatures the local susceptibility follows the Curie-Weiss law

$\chi(T)=\frac{C}{T+\theta}$ (1)

with a positive temperature $\theta\approx 500K$ (in agreement with earlier
result of Ref. Georges  and experimental data Sr2RuO4_NMR ). Following
Wilson’s result for the local spin $S=1/2$ Kondo problem Wilson ; Melnikov ;
Tsvelik , the temperature $\theta\simeq\sqrt{2}T_{K}$ yields the temperature
scale of screening of the local moment (Kondo temperature) $T_{K}$. Since the
dependence $\chi(T)/\chi(0)$ is almost universal for different $S$ Desgranges
, the abovementioned relation between $\theta$ and $T_{K}$ is also expected to
hold approximately for arbitrary local spin value. Therefore, for Sr2RuO4 we
find the temperature scale of spin screening $T_{K}\approx 350$ K, which is
much smaller than $T^{\rm ons}$, obtained by the authors. We also note that
very similar linear dependence of the inverse susceptibility is observed in
the other Hund metals: $\alpha$-iron ($T_{K}=50$ K for density-density
interaction and $T_{K}\approx 320$ K for Kanamori interaction) a-iron ; iron-
nickel , $\gamma$-iron ($T_{K}\sim 700$ K) g-iron , nickel ($T_{K}\sim 850$ K)
iron-nickel , etc.

Figure 1: Temperature dependence of inverse local susceptibility
$\chi^{-1}(T)$, calculated from the data of Ref. paper  for Sr2RuO4 (a) and
V2O3 (b). The inset in (b) shows inverse local spin susceptibility of the
single-band half filled Hubbard model on the square lattice with nearest
neighbour hopping $t$ and on-site Coulomb repulsion $U=9t$ (triangles) in
comparison to the inverse spin susceptibility of the Kondo model Wilson
(circles); the Kondo temperature $T_{K}=0.032t$ of the Hubbard model is
extracted from the fit of the low-temperature part of the susceptibility to
the Kondo model. Dashed lines show linear fits to the data.

For V2O3 the situation is more complex, since the inverse susceptibility shows
at $T\sim 600$ K a crossover (see Fig. 1b) from the Curie behavior
($\theta\approx 0$) to Curie-Weiss behavior with $\theta\approx 150$ K. This
crossover, however, is likely not related to the screening, but reflects
passing from a crossover regime to metallic one in the vicinity of Mott metal-
insulator transition for this compound V2O3 . To confirm this viewpoint, we
present in the inset of Fig. 1b the temperature dependence of the inverse
local spin susceptibility, obtained for the single-band half filled Hubbard
model on the square lattice with nearest neighbor hopping $t$ (on-site Coulomb
repulsion $U=9t$ is in the vicinity of Mott transition), showing that this
dependence is qualitatively similar to the one, obtained for V2O3. Therefore,
the screening scale of local magnetic moments in V2O3 is again given by the
Kondo temperature $T_{K}=\theta/\sqrt{2}\approx 100$ K, extracted from the low
temperature part of the local susceptibility in paramagnetic phase. The latter
value is also much smaller than obtained by the authors and has the same order
of magnitude as the temperature, at which the screening is completed, $T^{\rm
cmp}\sim 25$ K. This makes it reasonable to describe spin screening in V2O3 in
terms of a single energy (or temperature) scale, as it should be for a
screening process of a single impurity site, considered in DMFT. We note that
rather large Weiss temperature of local susceptibility of V2O3 ($\sim 600K$),
observed experimentally in nuclear magnetic resonance studies V2O3_NMR  in the
temperature range $T>150K$ may be related to the impact of strong
antiferromagnetic correlations on local susceptibility, which is absent in
paramagnetic DMFT solution.

The observation that for V2O3 $T_{K}\sim T^{\rm cmp}$ is in contrast to the
above described situation in Sr2RuO4, where $T_{K}\gg T^{\rm cmp}\sim 25$ K.
We note that such an inequality is also fulfilled for nickel iron-nickel , and
in that case this was attributed to underscreened Kondo effect, since the
Fermi level of nickel is close to the upper edge of the band. The origin of
strong difference of Kondo temperature and the temperature, corresponding to
completion of the screening in Sr2RuO4, requires further studies and
clarification.
Acknowledgements.  The work is partly supported by the theme “Quant”
AAAA-A18-118020190095-4 of Minobrnauki, Russian Federation.
Data availability. The DMFT data for susceptibility of Sr2RuO4 and V2O3,
analyzed here, are taken from Ref. paper . The data on the single-band model
are available within the present paper.
Author contributions A. K. is the sole author of this work and is responsible
for the conception and design of the work.
Competing interests: The author declares no competing interests.

## References

  * (1) Deng, X., Stadler, K. M. , Haule, K., Weichselbaum, A., von Delft, J. , Kotliar, G., Nature Comm. 10, 2721 (2019)
  * (2) Metzner, W. and Vollhardt, D., Phys. Rev. Lett. 62, 324 (1989).
  * (3) Georges, A., Kotliar, G., Krauth, W., and Rozenberg, M., Rev. Mod. Phys. 68, 13 (1996); Kotliar, G. and Vollhardt, D., Physics Today 57, 53 (2004).
  * (4) Mravlje, J. and Georges, A., Phys. Rev. Lett. 117, 036401 (2016).
  * (5) Imai, T., Hunt, A. W., Thurber, K. R., and Chou, F. C., Phys. Rev. Lett. 81, 3006 (1998).
  * (6) Wilson, K., Rev. Mod. Phys. 47 773 (1975).
  * (7) Mel’nikov, V. I., Soviet Phys. JETP Lett. 35, 511 (1982).
  * (8) Tsvelick, A. M. and Wiegmann, P. B., Adv. Phys. 32, 453 (1983).
  * (9) H-U Desgranges, J. Phys. C: Solid State Phys. 18, 5481 (1985).
  * (10) Katanin, A. A., Poteryaev, A. I., Efremov, A. V., Shorikov, A. O., Skornyakov, S. L., Korotin, M. A., Anisimov, V. I., Phys. Rev. B 81, 045117 (2010); Igoshev, P. A., Efremov, A. V., Katanin, A. A., Phys. Rev. B 91, 195123 (2015)
  * (11) Hausoel, A., Karolak, M., Şaşıoğlu, E., Lichtenstein, A., Held, K., Katanin, A., Toschi, A., Sangiovanni, G., Nat. Comm. 8, 16062 (2017).
  * (12) Igoshev, P. A., Efremov, A. V., Poteryaev, A. I., Katanin, A. A., Anisimov, V. I., Phys. Rev. B 88, 155120 (2013).
  * (13) McWhan, D. B., Menth, A., Remeika, J. P., Brinkman, F., and Rice, T. M., Phys. Rev. B 7, 1920 (1973); Poteryaev, A. I., Tomczak, J M., Biermann, S., Georges, A., Lichtenstein, A. I., Rubtsov, A. N., Saha-Dasgupta, T., and Andersen, O. K., Phys. Rev. B 76, 085127 (2007); Hansmann, P., Toschi, A., Sangiovanni, G., Saha-Dasgupta, T., Lupi, S., Marsi, M., and Held, K., Phys. Status Solidi B 250, 1251 (2013).
  * (14) Jones, E. D., Phys. Rev. 137, A978 (1965); Rubinstein, M., Phys. Rev. B 2, 4731 (1970).