Analysis of target detection via matrix completion

A problem of broad interest is the detection and localization of a target or object from its generated field. In this paper, a detection and localization strategy which exploits the structure of target fields is designed and analyzed. In taking advantage of this structure, one is able to reduce sample complexity requirements while maintaining good performance. In particular, an exploration-exploitation approach to target detection is proposed utilizing the theory of low-rank matrix completion for a decaying separable target field. The assumptions on the field are fairly generic and are applicable to many decay profiles. Our approach does not require specific knowledge of the field, only that it admits a rank-one representation. A performance analysis for localization is presented that characterizes a trade-off with sample complexity in the presence of noise.