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 Facebook

SPS on Twitter

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar