Capacity of Remote Classification Over Wireless Channels

Remote classification involves offloading complex object-recognition tasks from mobile devices to servers at the network edge. It brings to the mobile device the capability of discerning hundreds of object classes by using the computational and storage capabilities of the infrastructure. Remote classification is challenged by the finite and variable data rate of the wireless channel, which affects the capability to transfer high-dimensional features and thus limits the classification resolution. We introduce a set of metrics under the name of classification capacity that are defined as the maximum number of classes that can be discerned over a given communication channel while meeting a target probability for classification error. We treat both the cases of a channel where the instantaneous rate is known and unknown. The objective is to choose a subset of classes from a class library that offers satisfactory performance over a given channel. We treat two different cases of subset selection. First, a device can select the subset by pruning the class library until arriving at a subset that meets the targeted error probability while maximizing the classification capacity. Adopting a subspace data model, we prove the equivalence of classification capacity maximization to the problem of packing on the Grassmann manifold. The results show that the classification capacity grows exponentially with the instantaneous communication rate, and super-exponentially with the dimensions of each data cluster. This also holds for ergodic and outage capacities with fading if the instantaneous rate is replaced with an average rate and a fixed rate, respectively. In the second case, a device has a unique preference of class subset for every communication rate, which is modeled as an instance of uniformly sampling the library. Without class selection, the classification capacity and its ergodic and outage counterparts are proved to scale linearly with their corresponding communication rates instead of the exponential growth in the last case.