Learning Tensors From Partial Binary Measurements

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Learning Tensors From Partial Binary Measurements

Navid Ghadermarzy, Yaniv Plan, Ozgur Yilmaz

We generalize the 1-bit matrix completion problem to higher order tensors. Consider a rank- r order- d tensorT in RN ××RN  with bounded entries. We show that when r=O(1) , such a tensor can be estimated efficiently from only m=Or (Nd)  binary measurements. This shows that the sample complexity of recovering a low-rank tensor from 1-bit measurements of a subset of its entries is roughly the same as recovering it from unquantized measurements—a result that had been known only in the matrix case, i.e., when d=2. By using a certain atomic M-norm as a convex proxy for rank, we allow for approximately low-rank tensors and give error bounds based on the M-norm of the tensor. We prove that the theoretical bounds are optimal both in the M-norm bound and the size N . Moreover, we show the advantage of directly using the low-rank tensor structure, rather than matricization, both theoretically and numerically.

SPS on Twitter

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar