Compressed sensing for navigation data

• US 8,994,587 B2
• Filed: 05/14/2010
• Issued: 03/31/2015
• Est. Priority Date: 05/14/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Bolotski, Josephine A., Rowitch, Douglas Neal, Moeglein, Mark Leo
• Primary Examiner(s): Phan, Dao
• Application Number:
  US12/780,329
• Publication Number:
  US 20110279324A1
• Time in Patent Office: 1,782 Days
• Field of Search: 342/357.25, 342/357.4, 342/357.49, 342/451, 342/453, 701/207, 701/214, 701/468
• US Class Current: 342/357.4
• CPC Class Codes: G01S 19/30 code related G01S19/246 takes precedence
• CPC Class Codes: G01S 19/36 relating to the receiver frond end
• CPC Class Codes: Y10T 428/1186 with head pole component

Abstract

Methods, apparatuses, and systems are provided for processing positioning signals to obtain navigation information by applying compressed sensing.

Claims

1. A method, comprising:

sampling a positioning signal received at a receiver according to a sub-Nyquist sampling rate lower than a Nyquist sample rate for the positioning signal to obtain a compressed sampling, the positioning signal capable of being reconstructed from the compressed sampling to obtain an estimate of a position of the receiver; and

wherein within a given time period, the sub-Nyquist sampling rate corresponds to m number of samples and the Nyquist sampling rate corresponds n number of samples, m being proportional to log(n); and

storing the compressed sampling at a storage medium.

2. The method of claim 1, wherein storing the compressed sampling comprises associating the compressed sampling with a media content item.

3. The method of claim 2, further comprising:

initiating capture of the media content item at the receiver; and

initiating said sampling of the positioning signal responsive to said initiating capture of the media content item.

4. The method of claim 2, wherein associating the compressed sampling with the media content item comprises appending the compressed sampling to the media content item as a digital tag.

5. The method of claim 2, wherein associating the compressed sampling with the media content item comprises storing the compressed sampling as metadata of the media content item.

6. The method of claim 2, further comprising:

initiating transmission of the media content item and the associated compressed sampling to a remote computing resource for reconstruction of the positioning signal.

7. The method of claim 1, further comprising:

initiating reconstruction of the positioning signal from the compressed sampling at the receiver to obtain the estimate of the position of the receiver.

8. The method of claim 1, further comprising:

initiating reconstruction of the positioning signal from the compressed sampling at a remote computing resource to obtain the estimate of the position of the receiver by transmitting said compressed sampling to said remote computing resource via a communication network.

9. The method of claim 1, wherein the received positioning signal comprises a sparse signal.

10. The method of claim 1, wherein the compressed sampling comprises a random sampling of the positioning signal received at the receiver.

11. The method of claim 1, wherein the positioning signal is one of a plurality of positioning signals received at the receiver;

and

wherein the method further comprises;

sampling the plurality of received positioning signals according to one or more sub-Nyquist sampling rates to obtain a plurality of compressed samplings; and

storing the plurality of compressed samplings at the storage medium.

12. The method of claim 11, further comprising:

reconstructing the plurality of received positioning signals from the plurality of compressed samplings to obtain an estimate of a path of travel of the receiver over a time period.

13. The method of claim 11, wherein storing the plurality of compressed samplings comprises sequentially storing the plurality of compressed samplings in a circular buffer of the storage medium;

and

wherein the method further comprises;

retrieving a select compressed sampling of the plurality of compressed samplings from the circular buffer responsive to obtaining a position identification request, the select compressed sampling corresponding to a previously received positioning signal of the plurality of positioning signals; and

reconstructing the previously received positioning signal from the select compressed sampling to identify a position of the receiver indicated by the previously received positioning signal.

30. The method of claim 1, wherein said sampling the position signal and said storing the compressed sampling are performed at least during a first mode, and wherein the method further comprises:

during a second mode, processing the stored compressed sampling by initiating reconstruction of the positioning signal from the compressed sampling to obtain the estimate of the position of the receiver; and

varying operation between the first mode and the second mode responsive to a position identification request.

38. The method of claim 30, further comprising:

initiating the position identification request according to a position update time interval.

39. The method of claim 30, further comprising:

initiating the position identification request responsive to receiving a user initiated request to obtain the estimate of the position of the receiver.

40. The method of claim 30, further comprising:

associating the estimate of the position of the receiver with a media content item.

14. An apparatus, comprising:

a navigation enabled device, comprising;

a receiver to receive one or more positioning signals;

a storage medium for storing data; and

a processor to;

obtain a compressed sampling of a positioning signal received at the receiver according to a sub-Nyquist sampling rate lower than a Nyquist sample rate for the positioning signal, the positioning signal capable of being reconstructed from the compressed sampling to obtain an estimate of a position of the navigation enabled device;

wherein within a given time period, the sub-Nyquist sampling rate corresponds to m number of samples and the Nyquist sampling rate corresponds n number of samples, m being proportional to log(n); and

store the compressed sampling at the storage medium.

15. The apparatus of claim 14, further comprising an analog to digital converter to convert an analog state of the positioning signal received at the receiver to a digital signal comprising the compressed sampling.

16. The apparatus of claim 14, further comprising:

a media capture device to capture one or more media content items;

wherein the processor is further programmed to associate the compressed sampling with a media content item captured via the media capture device.

17. The apparatus of claim 16, wherein the media capture device includes one or more of a camera, a microphone, and/or a keypad;

and

wherein the media content item includes one or more of an image, a video, an audio recording, and/or textual content.

18. The apparatus of claim 16, wherein the processor is further programmed to:

initiate transmission of the media content item and the associated compressed sampling to a remote computing resource for reconstruction of the positioning signal.

19. The apparatus of claim 14, wherein the positioning signal received at the receiver comprises a sparse signal;

and

wherein the processor is further programmed to randomly sample the positioning signal to obtain the compressed sampling.

24. The apparatus of claim 14, wherein the processor is further programmed to:

initiate the position identification request according to a position update time interval.

25. The apparatus of claim 14, wherein the processor is further programmed to:

initiate the position identification request responsive to receiving a user initiated request to obtain the estimate of the position of the navigation enabled device.

31. The apparatus of claim 14, wherein the processor is further programmed to:

initiate reconstruction of the positioning signal from the compressed sampling at the processor to obtain the estimate of the position of the navigation enabled device.

20. An apparatus, comprising:

a storage medium having instructions stored thereon that are executable by a processor to;

sample a positioning signal according to a sub-Nyquist sampling rate lower than a Nyquist sample rate for the positioning signal to obtain a compressed sampling, the positioning signal capable of being reconstructed from the compressed sampling to obtain an estimate of a geographic location represented by the positioning signal;

wherein within a given time period, the sub-Nyquist sampling rate corresponds to m number of samples and the Nyquist sampling rate corresponds n number of samples, m being proportional to log(n); and

store the compressed sampling at the storage medium.

26. The apparatus of claim 20, wherein the instructions are further executable by the processor to:

initiate the position identification request according to a position update time interval.

27. The apparatus of claim 20, wherein the instructions are further executable by the processor to:

initiate the position identification request responsive to receiving a user initiated request to obtain the estimate of the geographic location.

32. The apparatus of claim 20, wherein the instructions are further executable by the processor to:

initiate reconstruction of the positioning signal from the compressed sampling to obtain the estimate of the geographic location.

41. The apparatus of claim 32, wherein to initiate reconstruction of the positioning signal from the compressed sampling, the instructions are further executable by the processor to:

initiate transmission of the compressed sampling to a remote computing resource via a communication network, wherein the remote computing resource is capable of reconstructing the positioning signal from the compressed sampling to obtain the estimate of the geographic location.

42. The apparatus of claim 41, wherein to store the compressed sampling, the instructions are further executable by the processor to:

associate the compressed sampling with a media content item; and

wherein the instructions are further executable by the processor to initiate transmission of the media content item to the remote computing resource with the associated compressed sampling.

21. An apparatus, comprising:

means for sampling a positioning signal according to a sub-Nyquist sampling rate lower than a Nyquist sample rate for the positioning signal to obtain a compressed sampling;

wherein within a given time period, the sub-Nyquist sampling rate corresponds to m number of samples and the Nyquist sampling rate corresponds n number of samples, m being proportional to log(n); and

means for initiating reconstruction of the positioning signal from the compressed sampling to obtain an estimate of a geographic location represented by the positioning signal.

22. The apparatus of claim 21, wherein said means for initiating reconstruction of the positioning signal from the compressed sampling comprises:

means for transmitting the compressed sampling to a remote computing resource capable of reconstructing the positioning signal from the compressed sampling to obtain the estimate of the geographic location.

23. The apparatus of claim 22, further comprising:

means for associating the compressed sampling with a media content item as a compressed sampling component of the media content item; and

wherein the means for transmitting the compressed sampling to the remote computing resource further comprises means for transmitting the media content item comprising the compressed sampling component.

28. The apparatus of claim 21, further comprising means for:

initiating the position identification request according to a position update time interval.

29. The apparatus of claim 21, further comprising means for:

initiating the position identification request responsive to receiving a user initiated request to obtain the estimate of the geographic location.

33. An apparatus comprising:

a processor to execute instructions; and

a storage medium having instructions stored thereon that are executable by the processor to;

obtain via a communication network, a media content item having a media component and a compressed sampling component, the compressed sampling component comprising a sub-Nyquist sampling of one or more positioning signals indicating a geographic location, the sub-Nyquist sampling obtained according to a sub-Nyquist sampling rate lower than a Nyquist sampling rate for the one or more positioning signals;

wherein within a given time period, the sub-Nyquist sampling rate corresponds to m number of samples and the Nyquist sampling rate corresponds n number of samples, m being proportional to log(n);

process the compressed sampling component to obtain the geographic location;

and

store the geographic location in association with the media component.

34. The apparatus of claim 33, wherein the compressed sampling component comprises a random sub-Nyquist sampling of the one or more positioning signals;

and wherein the media component comprises one or more of an image, a video, or an audio recording.

35. The apparatus of claim 33, wherein the instructions are further executable by the processor to:

obtain a plurality of sub-Nyquist samplings of a plurality of positioning signals indicating a plurality of different geographic locations; and

reconstruct the plurality of positioning signals from the plurality of sub-Nyquist samplings to obtain an estimate of a path of travel defined, at least in part, by the different geographic locations indicated by the plurality of positioning signals.

36. A method, comprising:

obtain via a communication network, a media content item having a media component and a compressed sampling component, the compressed sampling component comprising a sub-Nyquist sampling of one or more positioning signals indicating a geographic location, the sub-Nyquist sampling obtained according to a sub-Nyquist sampling rate lower than a Nyquist sampling rate for the one or more positioning signals;

wherein within a given time period, the sub-Nyquist sampling rate corresponds to m number of samples and the Nyquist sampling rate corresponds n number of samples, m being proportional to log(n);

process the compressed sampling component to obtain the geographic location; and

store the geographic location in association with the media component.

37. The method of claim 36, further comprising:

transmitting an indication of the geographic location obtained from the processed compressed sampling component to a navigation enabled device via a communication network.