Decomposition techniques for multi-dimensional data

Patent metadata

Field	Value
Publication number	US-2016232175-A1
Application number	US-201315023226-A
Country	US
Kind code	A1
Filing date	Sep 27, 2013
Priority date	Sep 27, 2013
Publication date	Aug 11, 2016
Grant date	—

Abstract

Original data that represents a real-world object or activity and organized along three or more dimensions is received. The original data is represented as a product of several multipliers including a sparse core, such that the sparse core has fewer non-zero values than a tensor representation of the original data, and one or more unitary matrix multipliers. Modified data is generated based on the original data using the multipliers. This includes compressing, or reconstructing missing elements in, the tensor representation of the original data, such that the modified data provides a description of the real-world object or activity that is less complete or more complete, respectively, relative to the original data.

First claim

What is claimed is:

1 . A computer-implemented method for manipulating multi-dimensional data, the method comprising:
receiving, by one or more processors, data organized along three or more dimensions, wherein the data represents a real-world object or activity; generating, by the one or more processors, a representation of the data as a product of a plurality of multipliers including a sparse core and a plurality of unitary matrices, wherein the sparse core includes fewer non-zero values than a tensor representation of the data; and generating, by the one or more processors, modified data based on the data using the plurality of multipliers, including compressing, or reconstructing missing elements in, the tensor representation of the data, wherein the modified data provides a representation of the real-world object or activity that is less complete or more complete, respectively, relative to the data.

2 . The method of claim 1 , wherein the data represents pixels of a digital image, and wherein the dimensions of the data include (i) position along a horizontal axis, (ii) position along a vertical axis, and (iii) color.

3 . The method of claim 2 , wherein generating the modified data includes reconstructing, by the one or more processors, respective colors of pixels of the digital image missing from the data to complete the tensor representation of the data.

4 . The method of claim 1 , wherein the data represents collaborative filtering data organized along the three or more dimensions including (i) user identification, (ii) item identification, and (iii) item rating.

5 . The method of claim 1 , wherein the data represents a Structure from Motion (SFM) reconstruction of a physical object, and wherein the data is organized along the three or more dimensions including at least several of (i) x-coordinate of a camera, (ii) y-coordinate of the camera, (iii) z-coordinate of the camera, (iv) pitch of the camera, (v) yaw the camera, and (vi) roll of the camera.

6 . The method of claim 1 , wherein non-zero values in the sparse core are arranged according to an ascending or descending order.

7 . The method of claim 6 , wherein generating the modified data includes applying, by the one or more processors, some but not all of the non-zero values of the sparse core based on an ordering of the non-zero values to compress the tensor representation of the data.

8 . The method of claim 1 , wherein generating the representation of the data as the product of multipliers includes executing, by the one or more processors, an iterative constrained optimization algorithm to determine values of the sparse core that produce a lowest Lp norm of the sparse core.

9 . The method of claim 8 , wherein the lowest Lp norm is an approximation to a strong orthogonal rank.

10 . A computer-implemented method for manipulating multi-dimensional data, the method comprising:
receiving, by one or more processors, data organized along three or more dimensions to define a tensor D with rank n, wherein the data represents a real-world object or activity; executing, by the one or more processors, a constrained Lp norm optimization to decompose the tensor D into a core S and a plurality of unitary matrix multipliers, wherein the core S includes fewer non-zero values than the tensor D; and generating, by the one or more processors, modified data based on the data using the core S and one or more of the plurality of unitary matrix multipliers, including compressing or completing the tensor D, wherein the modified data provides a description of the real-world object or activity that is less complete or more complete, respectively, relative to the data.

11 . The method of claim 10 , wherein the data represents pixels of a digital image, and wherein the dimensions of the data include (i) position along a horizontal axis, (ii) position along a vertical axis, and (iii) color.

12 . The method of claim 11 , wherein generating the modified data includes determining, by the one or more processors, respective colors of pixels of the digital image missing from the data to complete the tensor representation of the data.

13 . The method of claim 10 , wherein the data is product rating data organized along the three or more dimensions including (i) buyer identification, (ii) product identification, and (iii) product rating.

14 . The method of claim 10 , wherein the core S represents a sparse structure of the tensor D.

15 . The method of claim 14 , wherein a norm of the core S is a bound for all tensor unfoldings of the tensor D.

16 . The method of claim 14 , wherein the core S is a diagonal tensor, with non-zero values along a diagonal being ordered.

17 . The method of claim 10 , wherein executing constrained Lp norm optimization includes executing constrained L1 norm optimization.

18 . A system comprising:
one or more processors; a first non-transitory computer-readable medium storing thereon data organized along three or more dimensions; a second non-transitory computer-readable medium storing thereon instructions that, when executed by the one or more processors, cause the system to:
generate a representation of the data as a product of multipliers including a sparse core and a plurality of unitary matrices, wherein the sparse core includes fewer non-zero values than a tensor representation of the data , and
generate modified data based on the data, wherein the modified data is organized along the three or more dimensions, and wherein generating the modified data corresponds to completing or compressing the tensor representation of the data using the multipliers.

19 . The system of claim 18 , wherein the data represents pixels of a digital image, and wherein the dimensions of the data include (i) position along a horizontal axis, (ii) position along a vertical axis, and (iii) color.

20 . The system of claim 19 , wherein to generate the modified data, the instructions cause the system to determine respective colors of pixels of the digital image missing from the data to complete the tensor representation of the data.

Assignees

• Zhou Shuchang
• Google Inc

Inventors

• Zhou Shuchang
• Chen Liyong

Classifications

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• H03M7/3059

  Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F16/283

  Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP · CPC title

• G06T2207/10024

  Color image · CPC title